Have you tried printing a configuration page from the printer's control panel itself? (Located in Information -> Print Configuration) If the configuration page does not have those trays listed, then there is something wrong with either the trays or printer itself. Otherwise, see if there are some newer drivers for the printer available, as there could be a software conflict with something else on the computers...
You didn't mention this, but I assume it was working properly before?