Seems as good time as any to ask this:
I've never played a game of DF where the entire map wasn't entirely red for the caravans. Is that not normal?
Check your depot. It should be green, including some surroundings.
Any green square is accessible by the wagon (which is not implemented as of now). If you build a 3-tile-wide path to the depot, only the middle tiles will light up green. Any green tile is accessible.
Also, wagons can only move up ramps, not stairs. Check the wiki on ramps.
The entire map is red. Every map I've ever played, actually, which I find very, very odd now. The only thing that isn't red are the middle 9 tiles of the depot that are yellow. I have never seen these green tiles. I can't possibly imagine what could cause this over so many versions and saves; I'd just ignored it thinking it was unfinished or something.
I get caravans fine, though.