@CameronDuthie — sorry, I would NOT recommend changing to Windows, sorry if you misunderstood me. I was merely trying to say that changing servers is not the best option in my opinion, your first resort should be just trying to fix the issue on the current server, whether it’s Linux or Windows or anything else.
I wouldn’t change servers unless there are a BUNCH of problems (like @Vermaas just listed). Just having a problem with rewrite rules wouldn’t be enough for me to do that.
My next answer would be to look into the .htaccess file indeed, but since you’ve already done that and it doesn’t seem that’s working either…..
You could try to change the permalinks in your WordPress admin (settings -> permalinks). Change it to anything other than what you have right now, save settings, and change it back to what you want. It should automatically edit the .htaccess file for you, and if there’s something wrong, you should get an error. If you do, maybe it’ll give you a better insight in what’s wrong.