Did you get this starter recently from an auto parts store? If so, taking things apart will probably void the warranty.
Definitely sounds like your starter took a crap. Check your grounds like H.L. said and check the voltage on that new battery just so you have a warm and fuzzy and no doubts.
Take that starter back and have 'em check it or just give you another. Usually, starters come with some documentation saying something to the effect of, 'make sure your battery is fully charged before attempting to start motor with new starter. Too little voltage from undercharged battery can result in "starter death".'
-David
