I would have jumped in earlier, but I don't use Vista and I don't know what this icon is or if it is a Vista OS icon/message ?
However, I would have though it would have given a little more reason why it was blocked ?
The "Windows has blocked programs that require permission to run when windows starts" doesn't say what permission is required, so I was kind of hoping that there might be a windows event viewer entry that might give more information. Have you applied any additional security settings that might actually be blocking avast, etc. ?
There must be literally millions of Vista and avast5 users and this is the first instance I can recall of this problem you mention.
Check out this Microsoft KB article on this error and see if it is any help,
http://support.microsoft.com/kb/930367.