Permalink Structure Wreaking Havoc

Hi, I just moved a site from a dev domain to the live domain. Everything is up fine and running until I change the permalink structure to %postname%. That is how I had it set previously, I saw in another thread to edit the database to remove this. I have done this and the site works perfectly with the default permalink structure but the second I turn %postname% back on I get a cannot be found error.

Any tips on what I need to do to be able to reactivate the %postname% permalink structure as, as you would imagine this is vital.

Domain name is: treasureservices.com.au