Try switching to the WP default theme - if the problem goes away, there is something specific to your theme that may be interfering with the WP conditional tags.
The most common sources of problems are:
wp_reset_query option.It might be that your theme performs custom queries before calling the sidebar. Try the wp_reset_query option.
Alternatively you may have not defined your logic tightly enough. For example when the sidebar is being processed, in_category('cheese') will be true if the last post on an archive page is in the 'cheese' category.
Tighten up your definitions with PHPs 'logical AND' &&, for example:
is_single() && in_category('cheese')
Another source of confusion is the difference between the Main Page and the front page
Again, take care with your conditional tags. There is both an in_category and is_category tag. One is used to tell if the 'current' post is IN a category, and the other is used to tell if the page showing IS for that category (same goes for tags etc). What you want is the case when:
(this page IS category X) OR (this is a single post AND this post is IN category X)
which in proper PHP is:
is_category(X) || (is_single() && in_category(X)
See also: 'Writing Logic Code' in the Other Notes section.




