Motor just stopped working?

I got the DC Motor from the arduino starter kit and I attached it to a 9V Battery and it worked fine then it was getting slower so I replaced the battery and it doesn't spin I also had attached a propeller to it(I did not expect it to fly :P) any ideas why it doesn't spin?

9V batteries are for smoke alarms, and are just about useless for motors.

So, I should have 12V instead or what do you suggest?

What motor do you have? "starter kit" doesn't mean anything to me.

https://www.arduino.cc/en/Main/ArduinoStarterKit

What do the instructions in the starter kit recommend?

A 4xAA or 6xAA battery pack will probably work.

Note: never attempt to power the motor from a digital output, or the 5V Arduino output. You can seriously damage the Arduino.

But how come the motor was working with the 9V battery but then stopped working? or is the battery just too weak?

For a motor you need a battery pack capable of lots of current. Small 9V batteries are not, they
start to struggle at 50mA even, certainly really hopeless at several amps which is what you may
need for your motor. Rechargable 9V batteries are better, but none are designed for powering
motors at all.

Use quality rechargeable cells (AA or larger), or SLA or LiPo.

'Bargain' and unbranded batteries are simply dross, never touch them. Stick to rechargable batteries if possible,
they usually at least have a marked capacity on them.

Interestingly, the product page for the Arduino starter kit has a link to the motor specs.

The stall current is 2.3 amperes! Whatever power source and motor driver you choose must be able to supply and (briefly) handle this startup current.