Are you by any chance using a number from a previous carrier? Or is it a new number? Sometimes that affects it... I heard one person switched to Verizon and his new number would always get the original phone number's mailbox rather than his new one. It could be the service, or the number won't work.
Google tends to hold answers. Found this, which says that the phone will go to voicemail when using the EDGE network. See if you iPhone is doing something during calls would be something to look at. It could also be that you have poor signal strength,
I bought an iPhone yesterday and I'm already on my second one with a second SIM card. Set up was easy enough but when someone calls me it goes straight to voicemail. This is the same problem I had with the first phone and SIM card. I took the first phone back to AT&T and they replaced the SIM card. When that didn't work I took the iPhone back to an Apple store and they replaced the phone and reinstalled the second SIM card.
I just came home, went through the set up and it still goes straight to voicemail. A friend suggested that it might be in "airplane mode" but I checked and it is off.
Anyone out there with some advice? I'm getting tired of running from place to place and I'll bet it's a simple fix.
By the way I set it up with a new Mac Pro running OS 10.5.1
Thanks in advance.