The scheme you outline still allows trivial impersonation attacks.
And keep in mind this is not a complete authentication protocol. I'm just proposing a small change to fix the signing-not-random-nonce problem, so I assume the rest of the protocol context is kept.
Barring stupid mistakes from my part, if this is vulnerable to impersonation so is the article's.
A E B
-hello->
-hello->
<-nonce-
<-nonce-
-random->
-S(rand)>
-S(n^r)->
-random->
-S(rand)>
-S(n^r)->(nice diagram, by the way)
To prevent this, Alice must also sign the domain she's authenticating to. The article mentioned this, and maybe you had meant it to be implicit in your protocol, in which case: my bad.