404 errors on all links

Hoping someone can help, I tried doing a search but searching for 404 errors certainly shows a lot of different problems. I recently moved my blog to a new host, before I did I upgraded to the latest version. I did a backup of the database and restored on the new server. The main page of my blog works, new posts display and everything is fine, but if you click on any links they all are 404’s, posts, categories, pages etc. Nothing works. If I go into the admin panel I can see all the categories, I can see the custom pages I had and all the data is still there, they just aren’t displaying.

Any thoughts on where to look?