OK I just tried it with your code and it worked perfectly. One thing I did notice was that you must not have Option Strict turned on as I had to add a few CType commands to cast objects to the correct type.
EDIT: One other thing I just noticed is that I think you said you are passing in the full path for the OldFile argument - dont, it should just be the file name because you already have the rest of the path in the TheServerUrl argument. If you pass the full path in for OldFile as well then when you combine TheServerUrl and OldFile in the first line of your RenameFileOnServer method then it is going to produce the wrong path isnt it - and that may be where your code was going wrong.

I also modified a couple of other small bits just so I could get it to run but it was only small things like changing it so it doesnt try to run AddToLog or QuitFTPNow so they should not have made any difference to anything. Give this code a try and see what happens:

vb Code:
  1. Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click
  2.         RenameFileOnServer("FTP://OurFtpServer/Test/", "Test.txt", "Test2.txt")
  3. End Sub
  4.  
  5. Private Sub RenameFileOnServer(ByVal TheServerURL As String, ByVal OldFile As String, ByVal NewName As String)
  6.         Dim MyFtpWebRequest As System.Net.FtpWebRequest = CType(System.Net.FtpWebRequest.Create(TheServerURL & OldFile), FtpWebRequest)
  7.         MyFtpWebRequest.Credentials = New System.Net.NetworkCredential(SwapUsername, SwapPassword)
  8.         MyFtpWebRequest.Method = System.Net.WebRequestMethods.Ftp.Rename
  9.         MyFtpWebRequest.RenameTo() = NewName
  10.         Dim MyResponse As System.Net.FtpWebResponse
  11.  
  12.         Try
  13.             MyResponse = CType(MyFtpWebRequest.GetResponse, FtpWebResponse)
  14.  
  15.             Dim MyStatusStr As String = MyResponse.StatusDescription
  16.             Dim MyStatusCode As System.Net.FtpStatusCode = MyResponse.StatusCode
  17.  
  18.             If MyStatusCode <> Net.FtpStatusCode.FileActionOK Then
  19.                 MessageBox.Show("*** Rename " & OldFile & " to " & NewName & " failed.  Returned status = " & MyStatusStr)
  20.             Else
  21.                 MessageBox.Show("Rename " & OldFile & " to " & NewName & " ok at " & Now.ToString)
  22.             End If
  23.         Catch ex As Exception
  24.             MessageBox.Show("*** Rename " & OldFile & " to " & NewName & " failed due to the following error: " & ex.Message)
  25.  
  26.         End Try
  27. End Sub

Also as you can see I have modified your Catch block slightly so that it actually tells you what the error is instead of just saying "an error occurred"