That is seriously some Jedi help there. This is exactly what I was looking for, some sort of troubleshooting guide.
I walked through most of this then realized what I was doing wrong. I was entering the password I set up on the Treo as the password on my iPod. Turns out it was looking for the WHOLE KEY, not the password. When I entered in the 26 digit key, it WORKED!
It's not high speed, but for what I need it for, it's perfect!
Thanks again @ooxteme!