Yeah, I think that bold looks better with sans serif typefaces than underline, so that was a design rather than an ergonomic decision; perhaps not a correct one. I think underlined blue text is probably the "most linky" looking text, given the history of the web.
Personally, as long as they stand out from the text and are in color, I don't much mind. Maybe I've gotten used to non-underlined links because many designs seem to use them.
For what it's worth, on my design I've made the compromise of underlining them on hover.