Telecare medicine information systems (TMISs) aim to deliver appropriate healthcare services in an efficient and secure manner to patients. A secure mechanism for authentication and key agreement is required to provide proper security in these systems. Recently, Bin Muhaya demonstrated some security weaknesses of Zhu's authentication and key agreement scheme and proposed a security enhanced authentication and key agreement scheme for TMISs. However, we show that Bin Muhaya's scheme is vulnerable to off-line password guessing attacks and does not provide perfect forward secrecy. Furthermore, in order to overcome the mentioned weaknesses, we propose a new two-factor anonymous authentication and key agreement scheme using the elliptic curve cryptosystem. Security and performance analyses demonstrate that the proposed scheme not only overcomes the weaknesses of Bin Muhaya's scheme, but also is about 2.73 times faster than Bin Muhaya's scheme.