Seeeduino BT Shield cannot be detected by android phone

Hey guys,

I just got my Seeeduino Bluetooth Shield (http://www.seeedstudio.com/wiki/index.php?title=Bluetooth_Shield#Connecting_Bluetooth_Shield_to_Android_Phone)
And downloaded the libraries and tried testing it out (according to instructions on the link) with my phone (HTC Evo 3d), but my phone can't detect anything.

The TX led light on my Arduino is blinking a lot --- in the serial monitor it's all this unreadable text like :

eU?jRþ?üüü@~~`~0000ø??¡*Õ(ª('RÈü?üüü@~~`~0000?áøÀÀÀ@à?üüü@~~`~0000ü?üüü@~~`~0000?ãøÀÀÀ@``` ð?üüü@~~`~0000?ãøÀÀÀ@``` 0??0ø?üüü@~~`~0000?ãøÀÀÀ@``` 0??øÀÀÀ@`~~~00?0ø?üüü@~~`~0000??ÀÀü|``` 000?øüÀ?üüü@~~`~0000?ÃøÀÀÀ@``` 0??0øÀÀÀ@`~~>00?0ø?üüü@~~`>0000??Àüü@``` 000?øüÀÀ@``~>?00??üüü@~~`~0000?ÃøÀÀÀ@``` 0??0øÀÀÀ@`~~>00?0øÀ?á?üüü@~~`~0000?ÃøÀÀÀ@``` 0??øÀÀÀ@`~~>00?0ø??üüü@~~`~0000?áøÀÀÀ@``` 0??øÀÀÀ@`~~>00?0ø??ø?üüü@~~`~0000?áøÀÀÀ@``` 0??0

I'm assuming it's a signal for the module to be detectable, but I can't connect to it...
Any ideas on what I'm doing wrong?

Have you tried using your Notebook? A lot of Android phone have problems with simple (so called insecure) bluetooth devices. The good news is that there seems to be a work-around possible with a special programming trick on the Arduino. But try first to connect with the PC because if there's no connection you probably won't be successful on the phone too.