I have much the same problem with AT$T, but I live in the middle of a bustling metropolis called Los Angeles (maybe you've heard of it). It is so annoying that the voicemail alert comes through fine, but not the original call.
__________________
Samsung Captivate (new love)
HTC Tilt 2 (for sale, soon to be gone)
LG Incite (long gone)