I'm having the same issue as you. I've plugged in the 5V to VCC on the JY-MCU, and GND to GND, both from the arduino. With just this configuration, we should be able to see the device in a list of bluetooth devices waiting to be paired, right?
I've also tried creating a little serial program (like you did), with no luck. Did you ever get this to work? Following the steps at the pinguino link didn't work.