I was talking to someone who trained with Ueshiba about his and he said that there was usually very little space on the mat when he was over there - you had to get up quick after being thrown as you knew that a second later someone would be thrown down in the same space.
Previously I've done exercises where you just ukemi down the length of one mat, then turn and ukemi back - so if you have about two mats between you and your nage you should be OK.
Of course a lot depends on how far Nage wants to throw you! There is something to be said about throwing uke at your feet (so that you can strike them when they're down). However this often results in a higher propensity of break falls rather than ukemis and can be very tiring.
Lack of space definately is good for spacial awareness - though when I've trained in small areas I have missed that flying through the air feeling. However, most real fights I've been in have been in very cramped spaces - night-clubs or pubs. We're lucky at out dojo, having a massive hall, but I often resitrict the numbers of mats we put out to make sure people get this idea of spatial awareness.
I once trained in a dojo where the ceiling was the main concern because it was so low! (had to watch your feet during a ukemi!).