Dimwhit,
I received my iPhone 4 as a gift last month and registered it for the free Mobile Me account, which worked great. I was able to use Find My iPhone A-OK. Then I exchanged that iPhone for one with higher storage, and the Find My iPhone account stopped working. It could not locate my phone. I figured it had to still be connected to the first device I had purchased, so at the Find My iPhone website, I deleted the first device. I tried to register my current phone and only got a message that said Device Not Registered when I tried to check on the site to see if it worked.
Like you, I tried everything that Apple recommended -- several times! Finally, I figured out that what you need to do -- what worked for me anyway -- is delete your Mobile Me account from your iPhone. Re-add it, but right after you re-add it, PRIOR to pushing save, switch your Find My iPhone to OFF. Then Save it with Off selected (to where it will not allow Find My iPhone). After you've saved it, switch that button to On, and you will get a confirmation at the bottom of your iPhone screen asking to Allow the Find My iPhone to use your current location and blah blah blah, and then you click Yes, and you should be good to go!
It took me such a long time to figure out because when I would re-add the account, On was already selected to allow it, and I'd just push Save. Then when I was trying to switch it to Off (because Apple recommended this to troubleshoot this problem), the switch would go to Off for a split second and automatically go back to On. I'm not sure why it did this, but it took me having to initially save the account to NOT allow it in order to eventually get this to work. In other words, slide your button to Off BEFORE you push Save, then change it to On after; try that.