One of my best sites went from 8 sitelinks to 4 mini-links on the key search, and I noted other changes to sitelinks sprinkled around, too. I'd say Google made overall changes to the sitelinks algo and what you saw is not specifically aimed at your site.

Here's the kicker...

At www2.sandbox.google.com my site still has sitelinks.

In Google Webmaster Tools, my sitelinks are still showing up.

But when performing a normal keyword search in Google, sitelinks are gone.

Strange...

I'm thinking there might be a few bugs the sitelinks algo! For my particular keyword, my site is the most relevant. I'm not just saying that because I'm #1, but I keep close tabs on the competition and I have more information, better information that is updated more frequently than the guys beneath me. While this sounds subjective on my part....I can assure you that I'm 20 steps ahead of the competition. This is why those guys gave me sitelinks well over a year ago in the first place, right?

I have been doing this every single day now for well over 2 years. I'm completely anal about being one step ahead of the competitors with regards to most relevant info on my site.

[edited by: tedster at 7:56 pm (utc) on Aug. 27, 2009]

On a side note Ted...

Did you notice any traffic variations from when you had sitelinks vs post sitelinks?

Yes, the new mini-sitelinks and anchor text that Google just chose seem to be performing better for us than the previous full sitelinks did. Out of the eight we used to see, only a few were really of interest to most people.

We know that sitelinks vary by query term -- and that what we see in WMT is never a guarantee that actual sitelinks will show up in a search result, especially for generic keyword searches. I can only guess at their direction, but I'm pretty sure that the tracking data that Google collects on sitelinks is now being refleected in this change.

What's interesting to me in this current change is that Google seems to have chosen more links that are not in the site's main navigation, but that are internal pages of strong interest.

Last night I noticed they changed my sitelinks around a bit.
That's why I was so surprised they disappeared today. Two of my most popular posts were in the sitelinks.
(with the most links/linkbait from social media sites).

I have noticed since Jan'09 people have been reporting on various forums of losing sitelinks. At first I thought it was an indicator of my site not being as strong due to new algo tweeks....but now I'm thinking that a condition in the new/tweeked algo was not met, and that's why mine disappeared.

I wonder if I should focus on trying to gain deeper links to older popular posts?