I've been in a position where I've painted myself in to a corner and have had a hard time figuring out how go get myself out of it. I think you've already taken the first step in fixing the situation. You've taken ownership of your mistake and it shows that you care about your work. In a case like this it's not about blame. Explain to your boss why the program shouldn't be used and the ramifications if it is used as it is. Will the program take the server down if a lot of people use it? Does it give bad data or mangle it? Look at the program and if it does do what its been designed to do then maybe you need to look at the reason why you're not satisfied with it. If you're not the one setting the priorities then you need to take that in to consideration when you're setting out to refactor a program.
I did it once, the boss knew that the program needed to be optimised and I was lucky in that part. If you decide to redo the program, since you already know what it's supposed to do and probably have a good idea on how to optimise it so its better more maintainable code, take the time to plan ahead on what you're going to do to reach your goal. Then to make an obscure reference from Thinner, "Eat your own pie."
in reply to what to do when you screw-up?
Update: Tanktalus makes a good point. Don't feel guilty and don't feel like you have to rewrite the entire program. Sometimes its best to let it be and when you have time to kill, that's when you rewrite it.