Try switching off 3G in Settings -> General -> Network and seeing if that allows you to make a call.
If you jailbroke it and unlocked it with ultrasn0w, then there may be a compatibility problem or a random glitch.
If your phone is not jailbroken or you wouldn't mind redoing the jailbreak, I would suggest restoring the phone using your computer to wipe the phone and put the latest firmware and baseband on. It would rule out any random software issues. If it still happens after a full restore, then there is a hardware problem and there won't be much else you can do about it besides taking it to a repair shop.
You could also try resetting network settings if you don't want to do a full restore. It resets your phone network settings and clears all of your saved wifi passwords. That might clear up the problem too.
Settings -> General -> Reset -> Reset Network Settings
The network settings reset is safe to do even on an unlocked phone.