|You might have to go to the Folder options first, search the filetype AVI and reset this to it's default setting.|
Sometimes windows need to restart, to get these thing set correctly.
Then again go to the folder options and search filetype AVI again. Choose change and select VLC. Click ok.
To make sure, this setting gets done correctly, you might have to restart again.
Month ago, I had such problem with another filetype and got it to work as decribed above. Ah btw, I don't know, whether this kind of icon association is also stored in the IconCache.db, which is stored in \Programs and Settings in your user profile folder. Simply search for IconCache.db and delete it. It will be recreated automatically during windows startup.
Hopefully that helps.
Please send a reply, if you solved the problem !!!