There so many sitelink formats out there these days, that I'm never quite sure which is new and which isn't :) Pretty sure I've seen those before though.I believe Google has some sort of "confidence level" which affects the size, number and format of sitelinks - so changes could indicate a change in that confidence level.
Msg#: 4440157 posted 10:05 am on Apr 14, 2012 (gmt 0)
New sitelink format tomorrow with more descriptions. New sitelink format next week with short descriptions.
etc. It's Google's business, focus on yours for better results.
Sitelinks tend to occur when a page is perceived as an index or authority piece and has aggregated a greater amount of rank in relation to the rest of the site. This happens naturally when your category links are sitewide.