Finally got around to installing the 3.1.2 firmware on my iPod.
Everything else is downhill from there. Open up PwnageTool, pick your model, find your firmware and that's about it (unless you want to change boot logo, etc.)
Then restore your iPod with the new [custom] firmware with iTunes. In iTunes, go to your iPod on the left hand side, hold shift and press restore. Find your firmware and that's it.