Android Market ---> Google Play
So this morning I tried to access Android Market and a new screen telling me that it was being upgraded to google Play. I, in my infinite wisdom, decided to close it off rather than accept so that I could have a quick google to see if it was legit and not the spawn of this demon-malware that anti-virus companies are constantly trying to convince us exists. So anyway, the result of this is 2 icons: Android Market and Google Play, both of which say "this application is not installed".
The only way I could get round this was as follows:
Download a market .apk from somewhere (fairly) reputable like XDA
Go to Settings>Applications>ManageApplications>All>Market and then force stop and clear data and cache.
Install the .apk file
open market a couple of times and it will offer the acceptance screen again.
I had tried rebooting and all the obvious solutions but this is the first thing that actually worked! Hopefully it'll be of some help should someone else have the same issues