Well, I tried with TWO SIM cards of non-official carriers (even *resellers* of non-supported carriers: a german simyo SIM and an italian WIND SIM) and it worked. Reliably. And I had been fighting for a few days to no avail to get it working.
The idea is to deactivate facetime/imessage, and THEN update the information in your contact book: Change the label of the old number to "cellular" and the label of the number you want to use to "iPhone" - there must be only one iPhone, I verified with two "iPhones" and it did not work.
Double check that in Settings -> Mail,contacts,calendars -> My Info you select your own contact card, otherwise the Facetime/iMessage servers do not know which number to activate. Check that the number is in international format with the GSM IDD shortcut "+" in place of the IDD "01" or "00" (that's the only way to get it really realiably working from a mobile phone). This may sound complicated and in fact the iPhone could just use the number stored in the SIM for this, but whatever. (Some SIM do not give this information correctly.)
After this, you may want to extract and reinsert the SIM, I do not know if this is really necessary, and you can now reactivate iMessage/Facetime. ACCEPT that you are going to send the SMS (I think that there is one outgoing from the iPhone and one ingoing for the activation process). Then wait a bit. For a few seconds/a couple of minutes the iPhone may still show the old number (if you are switching from another SIM) while it is "waiting for activation", but eventually it will activate and show the right number. YMMV: Once it activated iMessage immediately and Facetime only after a few minutes.
Of course there may be _other_ reasons for no proper activation, but at least this solved the problem for me. No restore, no "erase all settings", nothing more annoying that just checking that the information was indeed correct and unambiguous.
Roberto