Without seeing the page, hard to speculate.
But it sounds to me like you may have a border-bottom: 1px solid blue;
being applied. Perhaps add border: none;
. text-decoration: none !important
is right, it's possible that you have another style that is still overriding that CSS though.
This is where using the Firefox Web Developer Toolbar is awesome, you can edit the CSS right there and see if things work, at least for Firefox. It's under CSS > Edit CSS
.