It is likely you are solving an existing route layer after rebuilding the network. Most likely the element ids of the network changed and now the stops point to wrong locations. It could also be that you are loading locations that had been previously snapped to the network, again it may have used the older locations. So in the NA Window, right-click on the Stops sub layer and then choose the option to re-locate all the stops. Then re-solve. Hopefully that will give you the correct results.
Another possibility is that your impedance attribute is now returning a cost of zero for some (or all) of your edges. With zero-cost edges, *any* path will be a "shortest" path, and thus you may get these winding paths such as you see here. I have seen "haywire" results like this many times, and this is usually the reason. Please check your impedance attribute values for the edges along the given path (using the Network Identify tool), and if this is indeed the problem, update your attribute evaluator to return the correct (non-zero) values and rebuild.
Okay things are working again. I hadn't mentioned that I was actually using ArcLogistics 9.3.1. I thought I had the same issue with network analyst from arcmap but when I try it this morning I'm not having any problems with it. In ArcLogistics I had to create a new route to fix the problem. I'll repost to ArcLogistics to see if they have a known bug.
If it is working now then the isue is not zero costs in the network dataset. Most likely it was stale snapping information on the stops. ArcLogistics will not have a different reason as the underlying solvers are the same. Jay Sandhu