From a technical standpoint, ideally the logo should be readable on any of the colors that your office uses for that particular logo. The question of printing on white or black is typically necessary for certain branding principles, but in some cases there are examples that show certain designs that are required to be printed only on certain colors, and those decisions can be made on a case-by-case basis (for example, some universities in the US only print their logo on one of a subset of colors, usually 2-4 including black white grey and one of the main school colors).
At the risk of slipping into Marketing Lingo, a good logo really needs to communicate the identity and integrity of a brand. A great example is the arrow in the FedEx logo :
http://www.thesneeze.com/mt-archives/000273.php
The arrow is also present as the primary design element of the new fedex office logo :
http://www.brandsoftheworld.com/logo/fedex-office-0
In the latter, the three arrows converge to make another arrow. In the former, the arrow is integrated into the logo itself.
Logos communicate much more than just the name or icon of your company: they should tell someone what your company DOES. If nothing else, they should be easy to quickly recognize, even from far away or in very small places.
EDIT:
I discovered this today and thought I'd add it to my answer, it's a great reference:
http://brand-identity-essentials.com/100-principles