Hey all!
If you take a look at my Website just now:

http://geocities.com/DunbartonshireDancerz
You'll see the links along the top - What I'm wanting to do is have each link go a different colour when the cursor hovers over them.

For example, "Home" - Red, "Photos" - Orange, "Nightclubs" - Green, "Forum" - Blue etc.

I've tried tampering with the CSS but nothing seems to work, is it possible?

You can make classes for each different link:

This goes in your style sheet:

a.plain { text-decoration: none }

And this link would not be underlined:

This is <a class="plain" href="blah.html">not underlined</a>

You can make as many different classes as you want :D