My guess is that your boss doesn ont want you to rewrite the entire program. Lots of companies have these code heaps that are working and they have gotten to this point by Darwinian winnowing and tweaking over years.
in reply to So I'm in a bit of a quandary
If it is really important software with lots of bad things in there it sounds pretty likely that you will be unable to guarantee that a by-scratch rewrite will work the same. Or did you say there was a well-written technical specification document? :<
Depends on what your new feature is going to be, I'd think. If it is pretty modular and you can trace which global to update you might be able to get away with the pie and eat it too. If it is an all-embracing update and you have to manage the system in the future, a rewrite sounds more useful.. but remember, your boss didn't ask you to rewrite it, right? Why not discuss it with your boss and find out what the priorities are. If they ask for a hack then I guess you'll have to dive in and get dirty.
Though I've more often found people apologetic about code after the author has left the company ;) your boss probably will understand that refactoring the system around modular blackboxes with well-defined interfaces will reduce business risk and make it easier to add more features more quickly in the future.
If it is just garbage then you need to explain that you are having a lot of trouble understanding the code and could your boss sit down with you for some sessions to explain it. This might lead in to your enlightened suggestion "Why don't I just take the time to do a cleanup job on it so you can get back to work".