One thing I did which I dont see mentioned in this thread is to set the speeds for the type of road (freeway, main, side or something like that). It looks like it's used to compute the arrival time, which leads me to believe that it takes those speeds into account when searching for routes.

I believe the defaults were 55, 35, 25 for freeway, main roads, and smaller roads. I would suggest you guys set those speeds appropriately and then see if the system gives you a better route based on those numbers.