Sir, you are a genius!
Seriously, thanks for that. Totally forgot the body tag comes after the head tag

(That's how bad I am)
And the 'ol duplicate table tag - I'd have searched through the code for hours and never have found it. Sometimes it's better having a second pair of eyes. Many thanks again.
With those out of the way, the W3 threw up some more stuff - the font tags etc. In changing these values to an acceptable code for validation (ie using css) I've actually managed to give myself a bit more of a rudimentary grasp of css, which before was non-existent (not good).
I even picked up how to center a table using css, so it's all good! (I think)
So just in case anyone's interested (run away now

) here's the final version.
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<HTML>
<HEAD>
<meta http-equiv="Content-Type" content="text/html;charset=utf-8">
<TITLE>Test</TITLE>
<style type="text/css">
table
{
margin-left: auto;
margin-right: auto;
}
.verdana {
font-family: Verdana, Arial, Georgia
}
.colorchange {
color: white
}
.bigverdana {
font-size: 10mm; font-family: Verdana, Arial, Georgia
}
.smallverdana {
font-size: 3mm; font-family: Verdana, Arial, Georgia
}
</style>
</HEAD>
<body bgcolor=white text=black link=black alink=black vlink=black>
<table width=800 cellpadding=0 cellspacing=0 border=0>
<tr><td colspan=7 height=100 valign=bottom align=left class="bigverdana">test.com</td></tr>
<tr>
<td width=199 bgcolor=gray align=center class="verdana"><a style="text-decoration:none" href="link.html" class="colorchange">link</a></td><td width=2></td>
<td width=198 bgcolor=black align=center class="verdana"><a style="text-decoration:none" href="link.html" class="colorchange">link</a></td><td width=2></td>
<td width=198 bgcolor=black align=center class="verdana"><a style="text-decoration:none" href="link.html" class="colorchange">link</a></td><td width=2></td>
<td width=199 bgcolor=black align=center class="verdana"><a style="text-decoration:none" href="link.html" class="colorchange">link</a></td></tr>
<tr><td colspan=7 height=2></td></tr>
<tr>
<td width=199 bgcolor=black align=center class="verdana"><a style="text-decoration:none" href="link.html" class="colorchange">link</a></td><td width=2></td>
<td width=198 bgcolor=black align=center class="verdana"><a style="text-decoration:none" href="link.html" class="colorchange">link</a></td><td width=2></td>
<td width=198 bgcolor=black align=center class="verdana"><a style="text-decoration:none" href="link.html" class="colorchange">link</a></td><td width=2></td>
<td width=199 bgcolor=black align=center class="verdana"><a style="text-decoration:none" href="link.html" class="colorchange">link</a></td></tr></table>
<table width=800 cellpadding=0 cellspacing=0 border=0>
<tr><td colspan=3 height=12></td></tr>
<tr><td width=199 height=400 valign=top align=left class="verdana">
some
links<br>
will<br>
go<br>
here<br>
when<br>
they need<br>
to be<br>
added<br>
</td><td width=2 height=400></td><td width=599 height=400 valign=top align=left class="verdana">
Welcome to my website. I am having problems because I am an idiot and can't work out what's stopping my code being validated! If anyone can help me I'd be very grateful!
</td></tr>
<tr><td colspan=3 height=50 align=center valign=top class="smallverdana"><hr><a style="text-decoration:none" href="link.html">SOME</a> | <a style="text-decoration:none" href="link.html">MORE</a> | <a style="text-decoration:none" href="link.html">LINKS</a> | <a style="text-decoration:none" href="link.html">HERE</a></td></tr></table>
</body>
</HTML>