I never have had any success with the Categories Menu Web Part
showing column  types other than choice  or Yes/No. The extra columns
are added to the Categories view, which the Categories menu web part
uses, but it does look like that the Categories menu web part knows
what to do with columns  of any type  other than choice or Yes/No. The
additional columns do appear on the newsbweb.aspx when you create a
new site, and on the EditForm.aspx when you edit the properties of a
item in the Sites list.

I know that adding a site  column (of type choice) works. So have you
thought about creating your Department and Business Units as site
columns?

Not sure if I understand your last paragraph.
Department and Business Units are site  columns (currently of type  lookup).
If I make them of site columns  of type choice  yes they will work.

Currently we have about 250 departments globally and they can change name from
time to time.
So I was looking to use the lookup  type to put some smarts around it.
Initially this was based on that it was easy for me to export the list  of
departments from our system via crystal reports server then export to excel  then
import as a list into sharepoint.
(Kind of clunky but we are in proof of concept phase with our deployment not in
production, and still faster to do this process than type in 250 x 4 character
department names).

However based on what you are saying, looks like there might be some issues with
the categories  menu web part.

Sorry I didn't realise you were using a site  column. Yes - problem is
with the Categories Menu Web Part, so if Ms PSS don't come back  with
a solution, then you may have to make your Site column  a choice  and
have that as the definite source instead of the list imported  column.
Let us know how it goes.