I was just back at a univesity this past weekend and they had an apple store their, and they were still selling BRAND NEW iPod Video's 5G/5.5G in the 30GB, 60GB and 80GB size and they had like 20 in each size.
So you might get lucky checking out an Apple store otherwise you will probaly end up geting a used one, but you can get new cases from various retailers to make it look like it is new.