The carrier update files are stored in the following locations.

In Mac OS X:
/Users/[Username]/Library/iTunes/iPhone Carrier Support/

In Windows XP:
C:\Documents and Settings\[Username]\Application Data\Apple Computer\iTunes\iPhone Carrier Support

In Windows Vista:
C:\Documents and Settings\[username]\AppData\Roaming\Apple Computer\iTunes\iPhone Carrier Support\ in Windows Vista.

The version of the carrier settings is visible on iPhone and iPad Wi-Fi + 3G by tapping Settings > General > About and looking next to "Carrier". If you restore with a new version of the software, the carrier settings update may be included with that update. If not, iTunes will indicate that a carrier update is available after the restore.

Then, may I suggest reading these articles (just in case you haven't read them), and see if one of them could end your misery.

http://discussions.apple.com/thread.jspa?t...98264&tstart=15
http://www.iphoneincanada.ca/how-to/iphone...for-activation/
http://forums.redflagdeals.com/1phone-4-fa...ivation-920541/
http://modmyi.com/forums/unlocking-activat...n-t-mobile.html
http://discussions.apple.com/thread.jspa?t...98264&tstart=15
http://forums.whirlpool.net.au/archive/1500466

Like I have said, my Facetime is working as it should. So, I am not so sure if the solutions given above  would work on you. If one of them works, I would definitely be glad. But, one of my friends had a problem with his Facetime and found a solution from the first article. Happy reading.

On a sidenote, are your MMS and tethering features working as they should be? You might want to look at their configurations as well.

i tried almost all the methods above, but still no luck, and one more thing, my itunes does not prompt me to update my carrier settings when i plugged in my phone. fyi, im running the latest itunes and 4.1 os. 

yeah,reset network setting dosent work on my prepaid celcom, thats why fake APN still dosent work when i istall it,celcom seems lock their setting

i dont think celcom lock their setting.. last year im using 3gs and use fake celcom apn, but i still can browse the internet (even after restart). last few month i turn off the mobile data on iphone4, but still can use google map, the map still load.. at first attemp iphone will popup and tell ur iphone data is off or cant connect internet or etc, but if u force it and try again and again, then viola! u can access map with mobile data off or browse internet with fake apn..

i dont think celcom lock their setting.. last year im using 3gs and use fake celcom apn, but i still can browse the internet (even after restart). last few month i turn off the mobile data on iphone4, but still can use google map, the map still load.. at first attemp iphone will popup and tell ur iphone data is off or cant connect internet or etc, but if u force it and try again and again, then viola! u can access map with mobile data off or browse internet with fake apn..

can u use facetime? mine can use all only facetime cant use it.
hmmm fake celcom apn? can u give the setting.. jez want to compare with mine

emm,thats why i said celcom lock their sim card,i install fakeAPN because its drain my prepaid creadit,but after install i still can browse internet
so even manual insert APN setting it wont work,
mine cant facetime and my MMS also cant work,i just double check again 

The only difference I see with the new Celcom 9.1 carrier settings tht MMSC setting has an additional extension which is http://mms.celcom.net.my:80
The additional is :80
Also,the MMS Max message size defaulted to 512000
tried doing the "network settings" as recimmended by the links to recover Facetime but all the settings remained intact..can't be changed.

my Setting-Genaral-Network-Celular Data Network- all empty

All empty?maybe that's why u can't SMS?U'll hv to enter them manually then.

where's the celcom iPhone 4..?? Nomore insider's info...LOLZzz

This is what I have:
Celcom MMS Settings 
APN: celcom3g
MMMSC :
http://mms.celcom.net.my:80
Mms proxy :
10.128.1.242:8080
MMS Max Message Size: 512000

After inserting those settings,switch off ur phone and on again..then try to send mms to urself..hope it works for u.

FYI, carrier  9.1 add new setting:

Setting>phone>celcom service> blah blah blah....

i can sms but cant MMS,it try few setting but still cant =_=