Categorized mail in Outlook gone - the color labels, that is...

Hi,
After setting up a comprehensive color coded category system for my contact list in Outlook 2007 I saved my work, closed, then reopened Outlook and my contact list was properly categorized.
But when I opened my Outlook MAIL, I found that all the categorization there was completely gone. The mails still there, but not color labeled anymore.
Maybe, while working on the contact categories I unintentionally deleted the mail categories from my Master Category list. But if I understand well: deleting a Master category should still leave the labels unaffected. Right?
So how then could they disappear?

In the email menu the (favorite) search folder 'Mail for follow up' is shown in italic. And if I click on it an error message pops up:
'The operation failed. An object could not be found.'
What object? And how and where to find and restore it?
Maybe that could help me restore the categorized mail as well?

My most recent outlookbackup.pst was made just before re-opening outlook today, so it also misses the mail categorization.
On another computer I still have a backup of the same mail (till about 3 weeks ago), including categorization.
Is there a way, through export and import to copy those mails to my primary outlook file? Can export/import be filtered, so that I only select the categorized items?

Thanks for helping!

Sorry to say, Irene, but now I have three error messages instead of the one I complained about.

First of all: your first mail didn't respond to my problem. Not my category COLUMN is gone/invisible, but the category codes themselves are gone: the column is displayed but all 'color' boxes are empty. Gone where? And how to retrieve or re-import them?

Second: the recommended article
Error message when you select the inactive Categorized Mail search folder in Outlook 2003: "The operation failed"
did not describe my problem. I don't work with both Outlook 2003/2007 mixed, which is what this article tackles. And when I try to activate the 'Mail for follow-up' I get the same error message as before.

Also the recommended solution
Diagnose and repair Windows File and Folder Problems automatically
does not solve the problem.
On the contrary, the result is two new additional error messages:
1.
MATZWiz.exe - System error:
The program can't start because lts.dll is missing from your computer. Try reinstalling the program to fix this problem.
2.
Microsoft Automated troubleshooting Services
Fix it troubleshooting cannot continue because an error occurred. We're sorry but the diagnostic solution encountered a runtime error. Please try again later.

The new error message shown under 1 is not true. The file IS on my computer, in the Appdata Mats_Run-Temp folder. But what to do with it?

Hi Irene,
Purely by coincidence I found my 'color coded' email categories back: there were not gone but became invisible (namely white, no color) after the original red category had been deleted from the Master Category list. I saw the categories back when I changed my email to list view, with a column for categories. Then all the original assigned categories (reply, postpone, done) were still there. The only thing I had to do was: create the same categories again in the Master Category List, assign these codes to the items with the 'blanked out' categories and after that uncheck the tick box referring to that blank category.

I didnt try to repair the 'Mail for followup' error yet. No time, busy with (many) other outlook issues with higher priority now.

Also more or less by coincidence i solved the problem about the unaccesible searches. Didnt have to go through all the MATS issues or so. I simply rightclicked those italic searches (i had two of them), removed them, and created to new ones with the same name. Voila, problem solved.