For the curious, from what I've seen Terminal in Lion has 256 color support and (kind of shitty) full-screen support.
Granted, now that I think about it, I have seen a bug that makes Spaces-switching slow, so it's possible I'm just seeing the same thing in the full-screen animation.
To put it another way, the result is fine, I just don't like the transition.