Changing your Gmail password is not necessarily what you need to worry about because that wasn't compromised. HIBP told you your account at other places e.g. Heroes of Newerth was compromised. So if you used a password for that account that you also used in other places, then you're vulnerable. This is why password re-use is a really bad idea.