I worked for a startup that used Administaff.

Administaff basically sucks. They are expensive from a company perspective. The benefits (in Texas at least) are fairly poor and expensive.

Also, with noone on staff responsible for HR functions, there was a LOT of frustration when HR type questions and issues came up.