Hello, I'm also having a problem connecting (much less seeing the Arduino/Seeeduino Bluetooth Shield) with my android phone.
You wouldn't happen to be using Froyo/Android 2.2 on your phone would you?. I'm starting to see a few threads that don't mention 2.2 directly but most of the android devices that do work appear to be using Gingerbread/2.3. If that's the problem, then maybe we can get someone to start looking in that direction to fix things.
Bluetooth keyboards aren't seen by android 2.2 either. (and of course I have an LG Vortex which will probably never get a 2.3 update)
Winston