randomly trying to call will not ring once, beep and hang up
As strange as it may be, I did find a solution to this problem.  I noticed that if I switch data / 3G, the call would immediately go through.  I've tried this a lot of times where I couldn't call, switch off 3G and it immediately works.   

Also, I've recently switched to CyanogenMod from the native Samsung Android installation, and I don't recall this happening again.  Not sure if it is some kind of bug in Samsung's version of Android.  I'm also using a more recent version of Android, so that could also be the reason.