I listened to this this morning, played it in Audition and noticed that it's mono. Is the original file stereo, by any chance? If it is, then there's a much better chance of improving it, although I have to say that even with the adaptive NR on the mono sample, the results were not usable.
The problem with all the background noise is that it's not constant. If it was, it would be much easier to reduce. The reason that stereo would help is that if the voice is in one position in the stereo field, it's much eaier to retain just that position in the field and reduce the rest, using the Center Channel Extractor.