Resubmission Question

I had an old short story that I wrote a fwe years back. I submitted it around and got rejections all around. I stumbled across it recently and read it over (it was really bad) i rewrote and have submitted it to a few places and, although they were still rejections, they were not form rejections. Most of them talking about how well written it was but not quite right for them.

My question is, can I resubmit the story to the places that originally rejected it? (the places i think would fit the story best)

If so should I mention that I rewrote the story, or should i just resubmit it and see what happens/

Thanks in advance.

Great advice guys, Thanks!

I didn't even think of the title change, thats a great idea too!