cattledog:
Was there an issue with the baud rate causing the "garbage" on the phone, or was the issue solely the power supply?
So earlier in the day I tried running the sketch suggested to me in post #8 and you saw the result on the terminal. Nothing was working.
The baud rates were set ok, I believe. In the code, and also in the Serial monitor, they were set to 9600. I didn't mess with them.
With the same exact code, from post #8, but with the Arduino getting power from my power supply it worked. That's why I'm thinking that the supply was the problem. As soon as I wired the Bluetooth Module to get the power strictly from the Arduino and the Arduino was getting power trough the Vin and Gnd of the supply, everything worked fine.
Before wiring them this way, the Bluetooth Module was getting power directly from the power source and the Arduino was only getting power through the USB (which was connected on the front panel of my PC).