Password change after restoring from my Time Machine on my mid 2009 Macbook Pro

I just replaced my hard drive and restored my computer through my Time Machine. After doing so, my passwords will not work. I have tried rebooting at the start up by holding CMD+R but it will not take me to the utilities screen so I can get to Terminal. I do not know how or have any other way of getting into my computer. If anyone could help that would be great!