I have a navigation based on categories and certain pages appear under the same categories. That means they appear twice under two different menus. Does anyone see a particular problem with this, usability-wise?
I am a big fan of this. Redundancy in this case is good; it doubles the chances of the user getting their work done.
Basically, you want to go to some lengths to make sure users know that it's the same item in those two (or more) spots. You might even give the user cross-wise breadcrumbs ("also found under XXX"), though a simple list of categories at the top of the entry (like here on StackExchange) can suffice.
Another concern is if users need to know the status of an item--for example whether they've visited that page--and the status shows up as different in the two places it appears. This can happen due to incorrect design (e.g. if symlink directories on disk, the same page can have two distinct URLs) and is quite confusing.
No problem with this.
It's rare that category names are SO well defined and their scope SO tight that you would without hesitation be able to create an unambiguous relationship map between content and categories. Most e-commerce stores for example show items on several different categories. Just imagine if they didn't - trying to navigate to the right item using only categories would be a nightmare, and the site designers or content developers would have a task that would be frought with indecision on every item. And then what would you do when you wanted to add a gift category at Christmas time?
Imagine a gift card store - you might think they could split categories up into birthday, thank you, get well soon, leaving your job, etc. If categories really allowed no overlap, you wouldn't be able to add a popular range category (eg Toy Story), or an Oversized category. It's just an example, but it makes my point, which is that: not all content has only one attribute by which it can be of interest to all users