We are familiar with the special characters issue that you mentioned.
You can try to renames those titles without the : or using nfo files - http://support.boxee.tv/entries/510215-creating-an-nfo-file
Regarding to the specific shows Xena: warrior princess and Space: 1999.
1)Please rename the series Xena: warrior princess to Xena warrior princess ( without : ) and boxee will identify it correctly.
2) Space: 1999 is more problematic show since boxee related to the number "1999" as the release year of the series. please rename the title to Space.(1975) and boxee will identify it correctly.
I checked those titles on my boxee box with the titles that I gave you and it's worked perfectly (I have attached screen shot)
Please let me know if you have any issue with that.
Thanks in advance,