Last thing that comes to mind - I skipped it because it seemed kinda obvious - is to check that there's actually a call to the favicon.ico file in the theme.
E.g. check in the HTML source code (of any page on your website, doesn't matter which one) whether you see something like this:
<link rel="shortcut icon" href="http://www.example.com/wp-content/themes/yourtheme/favicon.ico" type="image/x-icon" />
If you don't see something like that, edit the theme's header.php file to include it. A good place would be right underneath the line containing the HTML <title> tag.
The location of the favicon file doesn't matter; it can be either in the webserver root folder (i.e. directly in the public_html or www folder) or just as in that example above, where I linked to the theme's folder, as that's very often where a favicon file is placed by the theme author (then again, it'd be strange if the theme's author didn't also include a proper favicon link in the theme's header file but hey, could be an oversight).
The 'Default' theme doesn't have a favicon though, so if you use that theme, you'll have to upload the favicon file, and also include that line in header.php pointing to where you put that favicon file (the webserver root is usually the best place).