Hi all,
I solved my problem, not sure if it will solve yours.
I used the "split" function to cut my polyline with a grid polygon such that all polyline segments ended at the boundaries in the grid. Should work for administrative boundaries or other shapefiles....
Don't forget you'll need to re-calculate the polyline segment lengths after this--use "calculate geometry" and make sure you're in the projection/units you want.