Menu Links Broken

Hi
I recently changed hosting company and imported my old wordpress site to the new hosting space but now none of my menu links work. Whenever I click one I get an error saying page not found on server. I’ve tried deleting the menu links and recreating them but still no joy, I’ve tried putting my permalinks to default and then back to post name but still nothing (although they do work when I leave them set on default!).
The pages all definitely exist still and are saved with the rite page names/slugs for the links to work.
Does anyone have any idea how I can fix this please?
Thanks
Jo
http://jojofield.com