What network and where are you located?
I used to have a similar problem when I was on Sprint and would forget to dial 1 and the area code for a number outside my local area (or, was it the other way around?). Anyway, it may be a dialing error on your part.