I personally waited for the new tradelines to appear on my report (bought by Sallie Mae right after I completed my rehab). Then I started disputing. And I disputed as often as I could. I know there is wording floating around the forums on what to say when you do dispute - I just said something along the lines of "student loan successfully rehabbed - collector agreed to removed negative remarks from credit report". Experian and Equifax happened pretty quickly - it only took me three or four disputes. Transunion took almost four years. However this is definitely a YMMV thing because I've seen anything ranging from they removed themselves before dispute, to people have not gotten them removed.
Have your loans been picked up by a servicer??