Deck naming is a real grey area, you'll always find disagreement. On PDCMagic especially there are many 'systematic namers' who always want deck names to tell you what the deck has in it. At the other end of the scale there are people who want deck names to be unique and interesting.
To answer your question, it depends on a number of things. If the deck has a core of cards that define it then changing some unimportant support cards doesn't make it a different deck. Pauper Storm is always going to have Empty the Warrens and/or Grapeshot, and any deck that hopes to win from those cards is always going to be named storm regardless of what other cards are included. A classic example is the deck FIsh. Fish is any blue based deck with cheap creatures and counter magic that is constructed with answers for the decks that the builder expects to see that day (i.e. the metagame). Two Fish decks could look entirely different from each other and share no cards at all. On the other hand it can be hard to tell Goblins!, Red Deck Wins and Sligh apart.
So you can call your deck anything at all, it's just polite to give credit to the original creator if your deck isn't really very different.