I was going to say try this thread there is a long discussion on it http://benefitslink.com/boards/index.php?/topic/53940-safe-harbor-401k-different-eligibility-allowed/#.VDWz1RYcVKo
If they cannot explain in detail why they assert an impropriety, or their explanation is incorrect, get a new service provider. One cannot expect advice to be correct 100 percent of the time, but starting off incorrectly within a fundamental function of the service provider is intolerable. You should let them know they are on the spot now, so they can push the question up to someone above the clerical responsibility level.