Ok, did your screen not display something like "Booting from CD-Rom...." during the boot up sequence with you WinXP CD in the CD Drive? You should press a key or enter to make it boot from the cd.
Now, if nothing like that came up, two things could be wrong. Either your bios is not set to allow booting from the CD Drive (which you should then change to allow this) or the WinXP "Reinstallation CD" you have is not a true Windows XP CD, but an OEM version or something like a "Recovery CD". Saying that, it should still work, but not always.
Now lets also confirm where the boot.ini file truley is.
In windows (from your first message I assume you can get into windows regardless of the error message):
Go start menu-> Programs -> Accessories-> Command Prompt (assuming you can see these on your start menu)
Type: cd c:\
( hit enter)
Type: attrib *.*
(hit enter)
Numerous files will be displayed, and hopefully boot.ini is listed. Should see SH Boot.ini listed. SH - means System and Hidden
If not, then lets see if windows is right, type: attrib c:\windows\boot.ini
(hit enter)
if it does come up, then simply type move boot.ini c:\
and (hit enter.)
Reboot, and see what happens. And give us some more details on the startmenu issue.
Oh, one thing, there is a chance you have boot.ini is both c:\ and c:\windows (which I think you do, or else you would not be able to get into windows). If that is the case, then do not do the move command. just rename the boot.ini file in c:\windows. But to do that, from the command prompt you will have to remove the attribs, and then rename it.
i.e. attrib -h -s c:\windows\boot.ini
(hit enter)
then
ren c:\windows\boot.ini c:\windows\boot_1.ini
(hit enter)
Good luck!