2007 is harder than with previous versions and their is no easy way to do
it. :(

try the category manager utility on
http://www.slipstick.com/outlook/olcat.asp

otherwise, you'll need to do it one mailbox at a time - add all the
categories to an item, save it to the desktop and zip before emailing it.
The recipients need to add it to the outlook them choose the option to
convert to color categories.

Dave, from today on it's very easy to synchronize your Outlook categories
even between different Outlook versions and also with colors, of course.
Please test the demo of the new Category Manager (link in my signature).