Mitch,
How many unique combinations would you guess you have? Per the Usage tips within the Combine tool's documentation it says the following:
"For formats other than ESRI GRID, by default, the output raster from this tool can only have a maximum of 65536 unique values.
You can increase this number by changing a setting in ArcGIS. On the Main menu, select Customize > ArcMap Options. In the ArcMap Options dialog box, click on the Raster tab and modify the Maximum number of unique values to render field to an appropriate value."
If there are more than 65536, an attribute table will not automatically be built.
-Eric