Ah ok.... just reinstall Lion on top of itself. It will recreate the Recovery HD.
Do a backup before the next paragraph just to be on the safe side.
Since you have a Lion install DVD, just boot from that by inserting the DVD, restart and press C when you hear the startup chime. The system will boot from the DVD. Then all you do is run the install again. No harm will come to your data or installed apps. After the reinstall is completed, you can check to see if you are able to get into the Recovery HD by restarting and pressing COMMAND - R when you hear the startup chime. If you boot into the Recovery HD, you're good to go with rerunning the Lion Recovery HD Assistant to create your USB thumb drive. If you can't, I'm not sure what you can do other than wiping your drive and starting over. OR find a friend with Lion and create your USB thumb drive that way.