tedster - 6:33 pm on Jul 24, 2010 (gmt 0)
What can I say - it happens. In the early days of sitelinks you needed a real powerhouse of a site to see sitelinks in the search results, but it's not that way today. What you are reporting is another sign that you may have a penalty - and you already suspect that anyway. It will be good news for you if the penalty gets removed.
This kind of ranking loss after major sitewide change (but keeping the same URLs) is pretty new - in fact, there are just a couple reports on the forums right now. So as far as I know, there's not enough of a user history to give any prediction for how long it will continue for anyone.
In fact, this kind of report is so rare that I am reluctant to say we have understood your situation. If I were you I'd keep going over all the technology and reports with a fine comb to be sure that something else isn't the real problem. And yes, most big penalties are related to links.
Are you using a CMS? Are you sure your server hasn't been hacked?