I tried various different links in the header, but couldn't get it to fall back nicely for other browsers. Eventually I noticed that the Sky Sports site had one which I guessed would work with all browsers so I copied their links and it seems to work nicely now.
So, just in case anybody feels the need, here are the header links:
<link rel="shortcut icon" href="/favicon.ico" />
<link rel="shortcut icon" href="/images/icons/favicon.gif" type="image/gif" />
The first one should be a windows icon file, and the second one is your animated gif.