The Unofficial Apple Weblog (TUAW)
Once an iPod gets to 2-3 years old it's outlived its original LiOn battery. On average, an LiOn battery is good for two years of heavy use (I'm now on my 3rd iBook battery).
When a new battery costs $100 plus shipping, and a new iPod is $200, it's not worth bothering with a replacement battery. Keep the old iPod as an external hard drive and buy a new device. Now that the replacement prices are considerably less, however, it's worth doing the swap.
BTW, Apple has an awful reputation for mangling iPods sent for a battery swap. The NewerTech batteries mentioned here are installed by the end-user. That's not entirely a bad idea.