Here's what i did, i turned off my phone, took out my sim card, placed my sim card onto another phone, tried dialling out, and it worked on my other phone
(If it does not work, its the card or your account's problem). I placed the sim card back into my old phone and it returned to normal.
If that doesn't work, you can try the method described on this youtube link:
https://www.youtube.com/watch?v=B4rEUEWpJvg
If it still does not work, then you can try going to application manager, ALL, Uninstall Google Inc. (Which gives you updates all the time)
If it still does not work, you may have to reset it to factory settings.
Finally if it still does not work, then i am afraid you will have to bring to to Samsung branch to get a technician to take a look at it.
Hope this helps!