I just ran into the same problem with a couple of my sites that are using Joomla. Even though I haven't made any significant configuration changes, this is the first time I've seen this problem since setting up my Google Webmaster account two months ago. My site is configured to use the OpenSEF plugin, which lets me assign a specific page when a 404 error is encountered.
For example, browsing to "http://domain.com/fakiefakie.html" will reroute me to "http://domain.com/" thanks to the SEO stuff I am using. Once I changed this so OpenSEF doesn't have a url in the value for "404 Not Found URL", Google verified me with no problem. It came as a suprise to me too, because I've been verified for quite a while. Dunno if this is new, or they just got around to checking me out. They aren't the most proactive when it comes to spidering me.
It appears that Wordpress supports the same functionality. According to Google, they enforce this because another site could masquerade as you. This isn't really clear to me but I still don't mess with "The Google," especially when I hear how frequently they ban AdSense accounts for unclear reasons.
http://www.google.com/support/webmasters/bin/answer.py?answer=35229&query=404 returns 200&topic=&type=
In their infinite wisdom, Google has decided that a dead-end failure page is preferably to a user-friendly redirect. Do you have a custom error page? If so, the browser may interpret the result as a success (200) instead of a page not found (404).
My choice was to disable the redirect until I come up with something better. The meta tag solution was a little complicated for my situation, since I am using a CMS.