It might be an improvement in this case, though it's common advice to limit the colour palette to a handful of colours. Blue text also doesn't always stand out against certain background colours.
Underlining links (particularly where there are many of them) can harm readability, which is why many popular websites do not do it, including the major search engines, Wikipedia and even Hacker News.
I doubt it, blue and underlined is pretty much a standard. I think it looks perfectly fine and clear. There's a reason most browsers' default stylesheet will make links look like that.