Hmm
After considering all the options, I JB my 3.1.3 with the original jailbreakme.com and then just installed software from iTunes instead of downloading it directly to the 'touch.
Interesting that software that "requires" 4.X, like TuneIn Radio install just fine when the 'touch is tethered to the Mac. Can't understand the error message when trying to directly download though?!?