If you just put the favicon.ico file in the root of your domain, IE doesn't have any way of knowing if it changed. To force an update, you need to use a
tag and point to a different filename than you previously used. The current filename is compared against the known filename stored in the Url History database. When IE sees the filename has changed, it will download your new icon.
Alternatively, you can ask your users to clear their history and cache (Tools->Internet Options->Delete Browsing History), which will also force IE to download the new file.
Standard Size for the favicon.ico is 32X32 8 bit color (256 Colors).