Hmm. A few months ago I would’ve assumed it was a WP issue, but they’ve fixed everything as far as I know. And I really beat the crap out my installs and haven’t had any issues with 2.5.1 yet so my guess is that its either some server configuration setting or its how the php interpreter is being used and was installed on your system.
Do you can try looking at your basic .htaccess directives like Options, DirectoryIndex, ErrorDocument, and maybe you’ll get lucky. Or you can try replacing that “Not Found” message with a phpinfo message (by setting up wordpress to output phpinfo from the 404.php) which could tell you if php is having some issues like pathinfo, and especially cgi stuff.
But now that I look at your blog, maybe it is WP.. I think I remember having the same kind of problem when trying to post in a category that is a subcategory of another category. I bet it would work if you posted into a parent category. Something is wrong when your latest posts are in your /category/archives/finally folder. Should be /category/finallly or else you will have to make pages.