Thanks to all of you who responded.
Yep, it turned out to be an .htaccess problem. I had one for the server in general but I had to create a new blank .htaccess file in the base directory containing all my WordPress stuff. I did this by creating a new text file and naming it .htaccess and adjusting the permissions on the file to be writeable globally so that WordPress can write on it.
Hopefully this helps somebody later on who finds this post on Google.