Colour Link Underlines probs

[mediaman_12]

For the head of my site I have a line of links, instead of doing graphics for these links I have used a non-underlined link style with a different colour for the underline.
Having 2 css text styles each with a a:hover sub style, and using embeded <span> tags

<div id="head-nav">
<span class="headnavtxt">
<a href="link.html" class="whitetext"><span class="headnavtxt">link</span></a></span> I <a href="link2.html" class="whitetext"><span class="headnavtxt">link2</span></a>
</span>
</div>

This works and looks just like I wanted (and what I was going to do using Gif's), except on the Visited links. On these the underlines no longer work. Any ideas?

link to site
Link to CSS

edited to make the HTML more clear

[Bill Posters]

Be sure that all id values (id="underlinestyle") have no spaces in them and don't start with either a number or an underscore).

Also be sure that you pseudo-classes are listed in the following order:

a:link {
...
}

a:visited {
...
}

a:hover {
...
}

a:active {
...
}

[mediaman_12]

Well all the pseudo-classes are in the right order, nothing has spaces, underscores or numbers in the names, and it still don't work .
I really dont want to go back to gifs, the client kept changing the names and order of pages, thats why I decided on the CSS route.

[Bill Posters]

Well all the pseudo-classes are in the right order...

No they're not.

a:link {
color: #B22222;
text-decoration: none;
}
a:hover {
color: Red;
text-decoration: underline;
}

a:visited {
color: #B22222;
text-decoration: none;}

a:active {text-decoration: underline;}

[mediaman_12]

Thanks for that, I must have mised the defaults. doh!
It works perfectly now.