The Applications you downloaded are locked to the device you bought them on now. That is the only device that can re-download them for free.
This prevents you from giving me your username and password and allowing me to get your apps for free, along with 100 other people. There is no protection on the iPhone to limit the number of times an app can be downloaded, however iTunes will check to make sure that your computer is one of the 5 authorized computers for your account. It's all about ensuring each purchased app is only on your authorized devices (sync'd by computers you've authorized).
This wasn't a problem until 3.0 which allows you to log into multiple accounts on your iPhone.
Try downloading a new application to that device. Then delete it. You can re-download it directly to the device for free.