Seems a little weird to be a server issue, but then again, anything is possible! Have you tried looking for anything like this in the Joomla! forums? Maybe someone else has had a similar situation.
And where are my manners? Welcome to the forums!
I just did a google search and came up with two entries. One of them had to do with Joomla! v 1.0.10 (the latest one). The entry was written in Dutch, but you can bet I'll be paying a little more closer attention to the Joomla! web site in the coming month or so!
So perhaps there might have been an issue with the router itself. Well, I've seen stranger things happen! Glad you got things working. (And it never hurts to learn something new!)
Thanks for the heads-up Thomas. While I don't have any of those in my sites, I'm sure there are people who do! So remember...it's YOUR responsibility to keep your site up-to-date...not TCH.