Did you put high traffic zones outside at all? Assuming your dwarves don't go outside much... And I'm assuming you didn't put them in those big long tunnels to nowhere?
I want to correct a misconception. The pathfinding speed has nothing to do with the numbers overall being bigger or smaller. If you zone the ENTIRE map as low-traffic, and even as restricted, you should expect to see the same things happen as normal or high designation.
The only change is that, to put it really simply: Dwarves will look for a way to where they are going in high-traffic before medium-traffic, and medium- before low-, low- before restricted. They'll still search in restricted areas eventually if they NEED to get there, but they'll search them last (in general). Zoning commonly used areas as high traffic can really help, but zoning infrequently used areas as high traffic is very counterproductive. Zoning rooms that dwarves never go to as 'restricted' can help, but it can hurt you really bad if you misuse it.
Like, let's say you have a refuse stockpile that you don't want dwarves wandering through, and you mistakenly zone it as 'restricted'. Now, your dwarves will only go through there as a last resort. But that includes your refuse haulers, who will search the entire map for your stockpile before they actually look at where it really is. That can cause a big slowdown.
On the other hand, let's say you have a large bedroom right along your main hallway. If a hundred dwarves walk past that place every day, you might consider making it restricted. The bedroom's owner will cause a little slowdown when he tries to get home, because he'll essentially search the whole map before he finds his bed, but probably it will be worth it.
Places that EVERYONE goes are good 'high traffic' candidates...like the booze stockpile, if you have one big one, and maybe the dining room. Just keep in mind that anyone who needs to walk past the dining room will say "Hmm, maybe my workshop is in here" along the way.
It's actually a lot more subtle than that, but meh...
If you want a real quick test to try this out, one thing to try is to zone your entrance as restricted. If you only have one entrance to your fort, and most dwarves don't go outside all that often, make like the first ten tiles of your entrance tunnel restricted. You can sometimes see a huge speedup just from this.
(reasoning: It doesn't really slow down dwarves who need to go outside, on their way out, because they're likely to search the whole fort first anyway. But it almost guarantees that nobody who doesn't need to go outside will even consider it.)