What font encoding are you using? \textunderscore is not available except in typerwriter fonts in the default font encoding, OT1, that is, in the font encoding you get if you don't or your installation doesn't explicitly specify another. However, it is available via T1 font encoding. Therefore, you might try explicitly setting your font encoding to T1 (add \usepackage[T1]{fontenc} before loading hyperref).
If that doesn't work, you might try some other fonts to the one(s) you're using, keeping the T1 fontencoding, eg, \usepackage[sc]{mathpazo} to load palatino fonts.
If that doesn't work (which would be very strange), try adding
\def\textunderscore{\char\`_}
to your code immediately after \usepackage[T1]{fontenc}.
Finally, if none of this works (and I'd be most surprised if it didn't), latex.ltx defines \textunderscore (almost) like this:
\DeclareTextCommandDefault{\textunderscore}{%
\leavevmode \kern.06em\vbox{\hrule width .3em}}
Try including those lines in your document preamble (again, after \usepackage[T1]{fontenc} and before loading hyperref). NB, the result won't look that great, but nevertheless, better than no underscore at all!