My company currently has a policy that anyone working 20 or more hours per week earns vacation, sick and holidays. We would like to stop this policy and allow only full time employees (working 40 or more hours per week) to continue these benefits. Can we do this? What kind of length of notice do we have to provide)? Also, can we tell them anything they have accrued this year to date must be used before the end of the year?

If these people are employees at will (they do not have written contracts) then the employer can change the terms of their employment at any time. Benefits earned before the change should be preserved because state labor laws usually require it. Reasonable notice should be provided. Some state like CA have strange rules for vacation benefits and counsel should be consulted if employer wants to take away accrued beenfits.