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?