I came a across this issue recently when I created a new SharePoint theme. After much trial and error, it turned out that a colleague who had created a new master page, had missed out the SharePoint theme control reference that renders the link to the custom theme css file. However this took a while to work out since there was so many other possible points of failure for the theme not taking effect.
Here I've listed some steps that can be taken to pin point the source of the problem with your custom theme. Before you start, you must understand the consequences of making changes through SharePoint designer. It is an important topic to learn about before touching your SharePoint site through SharePoint designer in any case.
Check your CSS code - best way to do this is to create <style></style> tags just before the end of the <head> tag. Put your css code inside and see if you get the desired effect. It may be the case of your CSS code being incorrect. Manipulating SharePoint look and feel requires precision CSS code. Someone without good understanding of the way CSS works will struggle to see changes their changes taking effect. If your CSS is the issue, then have a look at Heather Soloman's excellent CSS reference chart for SharePoint 2007. Also take into consideration that the theme also gets applied to the SharePoint configuration pages.
Apply/reapply your theme to your site- you can do this by manually applying the theme by going into Site Actions > Site Settings> Site theme.
Ideally you should have a feature to apply and remove the theme from your site. This is quick and easy to build and very easy way to have control over the theme application after the SharePoint site has been deployed. There is a known issue regarding applying a theme to web, which doesn't apply the theme to its sub webs. This is also where the feature receiver can come very handy as it could be coded to propagate the changes down the hierarchy. One you have this in place, you simply Deactivate and Active this feature followed by an iisreset (important for SharePoint to pick up the updated copy of the theme).
Check that your theme is being installed. Here is where SharePoint designer comes really handy. Connect to your site and you'll see a _Themes directory in the tree view.
SharePoint creates a copy of the theme and stores it inside the web object, in the database. Once you expand '_themes', you'll see the folder for your theme. Inside this, you'll find 'theme.css' and '[beginning of your theme name][some random numbers].css'. The latter is what's actually being used. You can open this file up and check the CSS to see whether this has been updated. Worse case scenario, delete both of these files off and try again (re-apply your theme). Usually, an iisreset forces these files to be flushed after the theme has been updated. The reason SharePoint reserves a copy of theme files has to do with the possibility of the web object being moved to a location where the theme doesn't exist. This would mean that the pages in this SharePoint web would loose their look and feel. Therefore the caching of the theme is important.
Edited 6th April 2010 - Recently I discovered another issue with SharePoint themes caching. I hand-coded a line in my theme.css file and discovered that at some point during the theme installation / provisioning, SharePoint tries to validate the CSS inside theme.css. In my case, SharePoint was stripping out tags that contained spaces around the '!important ' tag. Since I only making this change to new lines added, I thought that the reason I couldn't see my change through SharePoint designer was due to some caching issue. Only when I removed all the spacing around the '!important' syntax, did the attribute get accepted by SharePoint.
Check your master page - If you or your colleague have created a custom master page, check that the <SharePoint:Theme runat="server"/> tag exists. Also make sure that this tag appears bellow the <SharePoint:CssLink runat="server"/> link tag as it needs to override some of the css classes referenced by the CssLink tag.
Just to clarify, you should have the following in your master definition.
<SharePoint:CssLink runat="server"/>
<SharePoint:Theme runat="server"/>
You can also make sure that the browser side caching is turned off. I would recommend that as you introduce new images to your theme, you should give them a unique name. If you don't, at some stage you're likely to be confused by the older version of the image showing up. This may be partly to do with the fact that SharePoint creates a cached copy of anything inside your theme folder.
If you have something else to add to this list, please comment bellow.