The area is a 20' radius spread.
The general rules for magic (in the PHB) state:
The default shape for a burst effect is a sphere.
A spread spell spreads out like a burst but can turn corners.
So the effect here is definitely three dimensional.
Now, the spell states:
These waving members seem to spring forth from the earth, floor, or whatever surface is underfoot—including water.
Which doesn't state anything about what direction the tentacles emerge from, only what surface they emerge from.
Let us imagine a homogeneous surface well described by the function z=1/r^2 in cylindrical coordinates. This surface becomes vertical at the pole. Let us imagine the spell is cast by a caster living on the surface at (1,1,π), and that the area of the spell includes (1,0,0), ignoring line of effect issues. The surface, being underfoot, is affected, even the parts of the surface which are vertical, since it is the surface, not the surface's orientation at all points in space-time, which is specified by the spell.
and after casting:
(please disregard the gross errors in axis labelling and choice of coordinates, they are irrelevant here)
The surface, must, however, still be underfoot when the spell is cast. Fortunately, gravity is well-defined in D&D 3.5, and so discerning this can be done easily: surfaces facing away from local gravity are 'underfoot'. Thus the answer to the example question depends where in the multiverse you are:
Plane of Air: Does the caster think the wall is underfoot? He makes a DC 16 Wis check as a free action (retryable each round with a cumulative +6 bonus per consecutive failure), and if he succeeds this works. If he fails, he loses the spell, though.
Material Plane: Down's towards the Earth or other dominant local source of gravity. The walls are not floors, so the spell fails. If the walls are slightly tilted but remain parallel, one of each pair of opposite walls is also a floor and the other one is also a ceiling. Probably a little better than a 50/50 chance this works, since buildings are more likely to be narrow at the the top relative to the bottom than the other way around.
Abyss: The Abyss decides if it wants it to work. You're casting Black Tentacles, but you probably end up with something more like Evard's Spiked Tentacles of Forced Intrusion. Also the Abyss probably likes you slightly more. All in all, a good place to do this.
The Outlands: The wall is a wall, not a floor. The Outlands has an objective up and down and even if a city is built sideways and every inhabitant has spider climb they still know what way 'down' is. Even if you're in space, down is down is down. Down does not change; it is merely your perception of Down that changes. Down is truth. Down is life. Your players are correct and your spell fails.