Indeed. The valid combinations you can have are as follows, with the lengths ordered with the longest first, and the shortest last:
[64 x 2 x 2] - Requires 64x64 base
[64 x 4 x 1] - Requires 64x64 base
32 x 8 x 1
32 x 4 x 2
16 x 16 x 1
16 x 8 x 2
16 x 4 x 4
8 x 8 x 4
You also have to take into account the height of the blocks you are using - most starts, finishes, checkpoints and such are a 2x1x1 block. A simple way to check this is by comparing it to a platform block, or by trying to place the same block one step above them. If they are taller than the platform block (and thus, if you place the block then hit page up, the block placement cursor is red) then it's at least 2 blocks high.
Also, note that the underground - as in below the default level - counts in terms of the size of the map. For example, if you have a map which is 16 blocks long and 4 blocks wide, and you have the track dip down two blocks below the ground, that means you only have two blocks of space above ground. I took this into account when I was making my map, as it uses an underground section one block below the ground, meaning that I only had seven blocks of airspace to play with instead of eight.
I will mention as an addendum that the 'underground' CPs and multilap in Stadium are two blocks high, but I highly doubt anyone would try to make a map which is just fully 'underground' there.
Finally, terrain editing. With this, I would say that any terrain editing counts as part of the scenery - with maybe the exception of the ground/water in Lagoon, Valley and Canyon. So if you use Dirt in Stadium, the size of the dirt area must fit within the box, while making hills outside of the box in Valley or Canyon would most likely go against the rules.