I have now fixed this issue despite "trying everything", by the following:
First, copy any data (pictures and so on) that you may have on your phone to your PC as this will erase everything!
- Providing you have copied all your data, reset the phone back to factory settings (Settings > About > Reset your phoe)
- Allow the phone to guide you through the "First time use" wizard, but **do not** sign into Windows Live.
- "Buy" an app from Marketplace - at this point you are compelled to sign into Windows live but that's fine.
- After you have downloaded all the apps you want then you can go to Settings > Email & Accounts > Windows Live and tick the box to sync email (if you want to).
- Update your phone using Zune (phone > Settings > Update)
After doing all of that, I found that I was able to get apps, whereas before, any attempt to get any app failed. The key was NOT to sign into Windows Live when setting up the phone for the first time.
I hope this helps some one else to rectify the issue.