"I accidentally changed the date on my computer while looking at the calender, but corrected this a few days later. Surely this cant be the cause of the problem?!? If it is, then this is a most serious security problem."
This could be the problem. It might be that McAfee have built in a function that at a preset number of days before your software is set to expire it sets a "flag" to say something like "Inside the last 30 days of the license". Then no matter what you do to the system its locked to expire in 30 days. By fiddling with the calender date you may have triggered that flag prematurely which is now irreversible other than doing what McAfee says. This is to prevent an old technique of setting you system clock back a year to get another years free protection.
I can't offer any help to fix it other than what McAfee has already said.
however now you have a choice. Pay McAfee again or go the Freeware route??
AVG 6 click here is Free for personal use and is recommended by loads of people here
Sygate 5 Personal Edition click here is also Free for personal use.