You could do this a couple ways. One way would be to test for the existance
before you do the renaming. To do that:

Sub test()
Dim NameOfSheet As String
Dim NameToBe As String


On Error GoTo FoundItAlready
Let NameToBe = "Frogs"
NameOfSheet = ActiveSheet.Name
ActiveSheet.Name = NameToBe


GoTo SkipOver 'if you get to here, it works so don't execute the code below.

FoundItAlready:
Sheets(NameToBe).Select
ActiveSheet.Name = "SomethingElse"
Sheets(NameOfSheet).Select
ActiveSheet.Name = NameToBe


SkipOver:


End Sub

What the above code does is name the current sheet to "Frogs" but if the
sheet "Frogs" already exists, it names it "SomethingElse" and then names the
sheet you want to be "Frogs" to "Frogs". This is a one-time macro with no
loops and you'd have to build looping in and also create variables for the
name to change the old one to so that you don't then try to creat multiple
sheets with the name "SomethingElse" but I think you'll get the idea with
this. HTH. Let me know if you need additional help.