My iPhone 4 shows only numbers starting with +20 (Egypt's International code) with recieved SMSs and the only way to show contact names is to add +20 to all of my contacts (with an app) but that would make recieved "calls" show numbers and not names !!!

Any way to fix that ?

iPhone 4, iOS 4.3.3