This happened to my gf's mini several times-- we traced it back to a song that was encoded badly, because every time she played this particular track the iPod froze.
Follow the instructions on
this page.
Pay close attention to see if the problem reappears under specific circumstances (e.g., playing a particular track), and you may be able to isolate the problem.
Before sending it back, I would also recommend running the iPod Software Updater and wipe the 'pod clean and reloading it.
You didn't mention how old the iPod is, but if it's under a year you're still under warranty. After going through the steps above, I would recommend calling Apple Support.