While iOS upgrades are usually free these days, it hasn't always been like this. According to wikipedia, iOS 1.1.3 was a paid upgrade on iPod Touches (while being a free upgrade for iPhones).
No they are right. Due to some sort of accounting thing once upon a time on some of the first iPod touches there would be a small fee to upgrade the OS.