A few years ago I was hired by an employer with a six month waiting period on their 401k. When we negotiated for compensation, I asked to have the waiting period waived. They did it and it wasn't really a big deal. I still wasn't eligible for the 401k match for a year, but at least I could get the tax benefits. This was a small 70 person company.
I assume the waiting period is to simplify things in the case of a bad hire.