Similar for me.
After activating the iPhone 4, it saw the Microcell right away (and my old 3G stopped seeing it) but I couldn't make or receive a call.
I switched the iPhone to Airplane and back again, and then I could call it, but still not make a call.
I tried again a few minutes later, and making a call worked then too.
Try again, and good luck...