OK… I went traveling again to Malaysia at last month, and changed my sim card for 3 weeks. No problems with changing my phone number in iMessage and FaceTime using my above technique. See post:
https://discussions.apple.com/thread/3402546?answerId=16728799022#16728799022 above.
But when I returned home and put my Australian sim card into the iPhone, I had the problem everyone seems to have: can't change phone number in iMessage and Facetime. Activation would fail, and the in the iMessage settings, I could not change the phone number under "you can be reached for messages at:".
To clarify, I have an unlocked iPhone 4S 16GB. iOS 5.1.1.
I tried: changing Date & Time to automatically, restarting iPhone. USB plugging into computer to sync a few times. Didn't work.
The error I was getting was iMessage failed to activate, or something like that. iMessage was still working.
I was loathe to do a reset or get a new sim card, and decided to just live with it until iOS 6 was out. Maybe it was an iOS bug I thought. I could still send and receive messages, and was mostly doing this on my computer anyway.
But today, after 3 weeks in Australia, I turned on iMessage again, and it activated properly. I don't know how.
Aside from ignore the problem, the only thing I've done differently is change my iTunes Store Apple ID (linked to Australia) to the same one as my iMessage one. Normally, I use a different one (linked to USA). I seriously doubt this was even related, but that's the only thing I did. I had to do this temporarily to buy something from the iTunes Store Australia.
Again, once I could do this in iMessage, I could do so in Facetime as well (which was otherwise turned off).