I'm at a bit of a loss with this, I haven't seen anything as resistant to being resolved having tried the most common issues for this problem.
Can you check the msconfig again, startup list, you said the entry was there for avastui.exe, but is the box checked (as assume it was (or you would have said), but confirmation is better than assumption ?
Something else that we used to do in very early avast versions (4.x and 5.x) where there was this issue was to create a shortcut in the Start Menu > startup folder (essentially the command in the msconfig, startup tab), see image example.
For me on XP this would be the location - C:\Documents and Settings\David\Start Menu\Programs\Startup, I have no problem creating these startup shortcuts on this system.
However, for Win7 it should be here C:\Users\UserName\Start Menu\Programs\Startup, but you come up against a bit of a brick wall when trying to get into the Start Menu folder (bl00dy permissions). I use win7 on my netbook and I really don't like it. Hopefully you will have better luck or someone more familiar with win7 can point the way.