Hello damsel,
I do not think this is a Non-Genuine issue. XP's anti-piracy sub-system does not have any control over the Start Button or desktop icons. Also, XP only asks to be "Validated" (for it's Genuine status) when attempting to download some files from the Microsoft Download site or Office site. If it's asking to be Validated, it must be reffering to something else. More likely it's actually asking to be Activated but when you click on it, it just brings you to a black desktop.
This sounds to me like a bad install. I believe it would be a faster resolution, for you, to try installing again. Or you can report your question in the Windows XP Newgroups
http://www.microsoft.com/windowsxp/expertzone/newsgroups/reader.mspx or contact XP Support at
http://support.microsoft.com for additional assistance.
Sorry I couldn't be more help,
Darin MS