Keep in mind that the Kindle Touch supports the KF8 format. Kindlegen 2.5 (that you indicated you were using) produces a file that contains BOTH a mobi version and a KF8 version. If you're then using a Kindle Touch to view the output, you're looking at the KF8 version ... which almost certainly doesn't use/recognize the <mbp:nu> tag. At the time this thread originated, there was no KF8, so things are different now. You also need to know which version you're previewing.
<mbp:nu> still works for the MOBI side of things just fine. I just checked. The problem is, it definitely doesn't do anything on the KF8 side of things -- which is what you're probably seeing on your Touch.
The KF8 side is easy, if that's all your concerned with. In your source ePub/xhtml, just make sure the link is properly styled (inline or CSS) with the "text-decoration: none" attribute. This works on devices that support KF8 like the Kindle Fire.
I've even had success mixing the two methods to ensure it works in both the MOBI and KF8 versions produced.
EDIT: However, extensive testing with the Kindle Touch emulation mode of Kindle Previewer reveals that none of the above methods removes the underline. I can get rid of the underline in every single device mode except the Kindle Touch. Could be a bug of the Previewer or the Device itself. I don't have a real device to test it on.