Ensure that your latitude and longitude values are in the correct units (degrees for the second formula or radians for the first one) for the expression you are using, and the procedure should work as expected.

Can you provide sample data that does not work?

If you want to find the distance between two points just use this formula and you will get the result in Km, just convert to miles if needed.

Point A: LAT1, LONG1 Point B: LAT2, LONG2

ACOS(COS(RADIANS(90-Lat1)) *COS(RADIANS(90-Lat2)) +SIN(RADIANS(90-Lat1)) *SIN(RADIANS(90-lat2)) *COS(RADIANS(long1-long2)))*6371

Regards

Alternatively, you can create a VBA function and then loop through your table.

Add this code to a Module in the VBA editor:

CopyPublic Function DistBetweenCoord(Lat1 As Double, Long1 As Double, Lat2 As Double, Long2 As Double)
    'Cell Formula
    'ACOS(COS(RADIANS(90-Lat1)) *COS(RADIANS(90-Lat2)) +SIN(RADIANS(90-Lat1)) *SIN(RADIANS(90-Lat2)) *COS(RADIANS(Long1-Long2))) *6371

    With WorksheetFunction
        A = Cos(.Radians(90 - Lat1))
        B = Cos(.Radians(90 - Lat2))
        C = Sin(.Radians(90 - Lat1))
        D = Sin(.Radians(90 - Lat2))
        E = Cos(.Radians(Long1 - Long2))

        DistBetweenCoord = .Acos(A * B + C * D * E) * 6371
    End With
End Function

Now you can access this through code or in cell. Here is an example of in-cell:

Copy=DistBetweenCoord(C1,D1,C2,D2)

Here is how to loop through all possible combinations in another Sub. Output is in immediate window.

CopySub CalcAllDistances()
    With Worksheets("Sheet1")
        For i = 1 To 4
            For j = i To 4
                If i <> j Then
                    Debug.Print .Cells(i, 2) & " to " & .Cells(j, 2) & ": " & DistBetweenCoord(.Cells(i, 3), .Cells(i, 4), .Cells(j, 3), .Cells(j, 4))
                End If
            Next j
        Next i
    End With
End Sub

EDIT - To change output to Sheet2 try the following:

CopySub CalcAllDistances()
    Dim wks_Output As Worksheet
    Set wks_Output = Worksheets("Sheet2")

    Dim OutputRow As Long: OutputRow = 1

    With Worksheets("Sheet1")
        For i = 1 To 4
            For j = i To 4
                If i <> j Then
                    wks_Output.Cells(OutputRow, 1).Value = .Cells(i, 2) & " to " & .Cells(j, 2)
                    wks_Output.Cells(OutputRow, 2).Value = DistBetweenCoord(.Cells(i, 3), .Cells(i, 4), .Cells(j, 3), .Cells(j, 4))
                    OutputRow = OutputRow + 1
                End If
            Next j
        Next i
    End With
End Sub

Given a list of geographic coordinate pairs, you can implement the Haversine formula directly in Excel.

The simplest way to use this (or a more accurate, but I think it's not your case) formula consists into press Alt+F11 to open the VBA Editor, click Insert --> Module and then (copy and) paste e.g. the code kindly suggested by blah238.

Public Function getDistance(latitude1, longitude1, latitude2, longitude2)  
earth_radius = 6371  
Pi = 3.14159265  
deg2rad = Pi / 180  

dLat = deg2rad * (latitude2 - latitude1)  
dLon = deg2rad * (longitude2 - longitude1)  

a = Sin(dLat / 2) * Sin(dLat / 2) + Cos(deg2rad * latitude1) * Cos(deg2rad * latitude2) * Sin(dLon / 2) * Sin(dLon / 2)  
c = 2 * WorksheetFunction.Asin(Sqr(a))  

d = earth_radius * c  

getDistance = d  

End Function

There will be a new custom getDistance function (unit = kilometer) available in your spreadsheet which accepts four parameters, i.e. the two pairs of coordinates, as follow:

getDistance(latitude1, longitude1, latitude2, longitude2)

where latitude1, longitude1, latitude2, longitude2 should be replaced by their relative cell references.