When creating a new icon make it always include two sizes 16×16 (16 colors) and 32×32 (16 colors). First one for browsers location bar second size for desktop shortcut.
Simple png-to-ico converter: png2ico
png2ico favicon.ico --colors 16 favicon16.png favicon32.png