"ECDHE" means that the key exchange will use the Diffie-Hellman algorithm (over elliptic curves) with freshly generated DH elements; the last "E" stands for ephemeral. So while DH produces a shared key, it will work with randomly produced values, and nothing in DH will ensure authentication: the client has no way to know whether the DH public key it sees really belongs to the intended server.
To bring back server authentication, something else is needed. It is a signature: the server digitally signs its half of the DH key exchange. That signature uses the key which is in the server's certificate, and thus the signature algorithm depends on the type of that key. In "ECDHE-RSA", the "RSA" part relates to that signature: it says that it will be of type RSA (and implies, of course, that the server's certificate contains the corresponding RSA public key).
There is no such mechanism for client authentication. When the server requests a client certificate, the client will have to compute a signature and send its public key (as part of its certificate), but there is no relation between that client certificate type and the cipher suite. The reasons for that are:
Client certificates appear later in the handshake, after the cipher suite selection. When the cipher suite is chosen, the client does not yet know whether a client certificate will be requested at all.
A SSL server, in general, must be able to answer to the whole World, but when the client connects, it knows what server it is talking to, and can select an appropriate certificate in consequence (the server also sends a list of CA names to narrow down the client choices). Client certificates are a rarity in a Web context; in all generality, SSL servers ask for client certificates when they know that the clients already have certificates of an appropriate type (e.g. a bank server will ask a customer's certificate only if the customer is part of a program in which the bank ensured distribution of the said certificates). Therefore, there is no need for a dynamic negotiation of the client certificate type.
The cipher suite selection is all about choosing algorithms which are supported at both ends. If the server must sign, and the client verify, then the client must be able to understand the signature algorithm and thus its key type.
In practice, the client sends a list of supported cipher suites, and the server selects one of them -- a cipher suite that, of course, corresponds to the algorithms and key types that the server is going to use. Theoretically, the list sent by the client is ordered by "preference" and the server is supposed to honour that order, i.e. choose the first cipher suite in the client list that also fits the server's abilities. Not all servers are that courteous.
See this answer for an introduction to SSL/TLS.