Can receive but cannot make outgoing calls on an iPhone 5S
This happened in my iPhone 4S since one of iOS 7 updates, sent many messages on Apple's contact form, no answer and no fix to date with the latest iOS 8.3, I temporary fix it by dialing *#31#.

It shows a message "Setting Interrogation Succeeded, Calling Line ID Restriction Disabled" and then can call normally.