I agree that it makes more sense (to me, at least) to do as you illustrate. In fact on pg. 547 of The Camel Book, Ed.2 it says:

• Put a newline between a closing brace and else

So I've always done it that way.