Is it possible that my new iPod touch is a used one?
Phone AppleCare, they will have more details on the original purchase date, location and registration details. Then take this information to the reseller and demand your money back if it was sold as new. If they are an Apple Authorised Resealer consider reporting them to Apple for not following the correct sales procedures. 

In future I would suggest buying directly from Apple wherever possible.