The tethered RedSnOw jailbreak for 5.1 worked like a charm. I ran into a problem when I installed winterboard however. Following the automatic reboot, I couldn't get my iPhone into DFU mode to use the "just reboot" function. What am I doing wrong?
Well, good news for you. As from a few weeks ago, you are able to jailbreak your iOS 5.1 untethered, which eliminates the fact you've to "just-boot" the iPhone very time.
In order to do so, Jailbreak nation has published a very detailed and good tutorial on how to jailbreak your iPhone. I suggest you preform a untetheredjailbreak and try again. If things are still not working, please give some feedback with your errors so we can help you further.
There shouldn't be anything different about getting your device into DFU mode after a Cydia-initiated reboot compared to a normal reboot.
Generally if people have trouble getting into DFU mode, the causes can include: not having the latest version of iTunes installed, using a USB hub/a bad USB cable/a bad USB port, holding the buttons for the wrong amount of time (or pressing them too hard sometimes), or having faulty buttons.
Restore your iphone/ipod to 5.1 then jailbreak it again.