Ok found the issue. I had missed it. In addition to changing the declaration of the vars, there was a scope issue with the Excel object varin your loop. Since its not destroyed in the loop it will also cause the retension of the instance of Excel.

I wrote a variation of your code for testing and Excel now terminates properly without the GC calls.

Code:
Option Explicit On
Option Strict On

Imports Microsoft.Office.Interop

Public Class Form1

    Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click
        Try
            Dim oExcel As Excel.Application = DirectCast(CreateObject("Excel.Application"), Excel.Application)
            oExcel.Visible = False
            Dim oWBs As Excel.Workbooks = oExcel.Workbooks
            Dim oWB As Excel.Workbook = oWBs.Open(CType("C:\Book1.xls", String))
            Dim WSNames(oWB.Worksheets.Count - 1) As String

            For intIdx As Integer = 0 To oWB.Worksheets.Count - 1
                Dim oWS As Excel.Worksheet = DirectCast(oWB.Worksheets.Item(intIdx + 1), Excel.Worksheet)
                ' Load up the Array
                WSNames(intIdx) = oWS.Name
                ' Calculate the % complete and pass out to update the Progressbar
                'worker.ReportProgress((intIdx + 1) * CInt(100 / (oWBs.Count)))
                MessageBox.Show(WSNames(intIdx).ToString)
                oWS = Nothing
            Next

            If oExcel IsNot Nothing Then
                oWBs = Nothing
                oWB.Close(SaveChanges:=False)
                oWB = Nothing
                oExcel.Quit()
                oExcel = Nothing
            End If
            ' Pass out the Array of Worksheet Names to the completed BackgroundWorker 
            'e.Result = WSNames

        Catch ex As Exception
            MessageBox.Show(ex.Message, "Error", MessageBoxButtons.OK, MessageBoxIcon.Exclamation)
        End Try
    End Sub

End Class