That is indeed malware.

Are you using XP Home or Pro?

If Pro:
Do you also get this message when logged in as administrator (not as user with admin rights)?

If Home:
Does your user account have admin rights?