I'm thinkin' it's path related...
<link rel="shortcut icon" href="/ubbthreads/images/favicon.ico" />
I'll look into changing it to an absolute path...
Edit: I changed
<link rel="shortcut icon" href="{$config['images']}/favicon.ico" />
to
<link rel="shortcut icon" href="{$config['imageurl']}/favicon.ico" />
in the ubbt_header.tmpl file so that I'd get the full path to the favicon and still no joy

I do get the favicon on the index and the ubbthreads.php page but as soon as I drill deeper into the site, like to the postlist or showflat pages, the favicon changes back to the IE default. Maybe it's a browser bug...
Edit #2: I tested it with the default ubbt_header.tmpl file in Firefox and Safari -both retain the favicon no matter where you are on the board, so it looks like an error with IE...