I've just replaced the my battery too (30 GB Video). Though it was quite challenging to opening the iPod, it all went smoothly after that; except from a small incident when the small tool broke when attempting to remove the battery from the iPod back. I used the big one instead and it went all fine. I also skipped steps 7-9)
CAUTION: when removing the battery from the iPod back panel, watch-out not to damage the "hold button cable" . The cable is right below the battery, and might be glued to it.
I've connected the iPod to iTunes and everything is reacting fine. My iPod is recharging right now on its cradle :-)
Total handling time: 45 min max.
Thanks to everyone for the tips. Great web site!