I don’t think the problem had anything to do with your server.
It was probably that your new .htaccess file wasn’t writable, and on the new system it might have been by default.
.htaccess must be set properly so that wordpress can use clean urls. When you upgraded you probably dumped/overwrote your old .htaccess file. I had this same problem and fixed it in 2 seconds this way.
