It is perfectly valid (at least by HTML 4.01 and XHTML 1.0 standards) to nest either a <span> inside an <a> or an <a> inside a <span>.
Just to prove it to yourself, you can always check it out an the W3C MarkUp Validation Service
I tried validating:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">
<html>
<head>
<title>Title</title>
</head>
<body>
<p>
<a href="http://www.google.com/"><span>Google</span></a>
</p>
</body>
</html>
And also the same as above, but with the <a> inside the <span>
i.e.
<span><a href="http://www.google.com">Google</a></span>
with both HTML 4.01 and XHTML 1.0 doctypes, and both passed validation successfully!
Only thing to be aware of is to ensure that you close the tags in the correct order. So if you start with a <span> then an <a>, make sure you close the <a> tag first before closing the <span> and vice-versa.