Inserting a column before the last column

A very nice first effort. For the future, please remember that only the macro recorder needs the many Select statements to point a finger at what you are doing. Excel or VBA don't need them. Instead of Worksheets("MySheet").Activate: ActiveSheet.Range("A1").Select: Selection.Value = "MyName" you can address objects (cells, ranges, worksheets, workbooks) directly, like
Worksheets("MySheet").Range("A1").Value = "MyName".

Here is code which, by and large, does what you want.

Option Explicit

Sub InsertColumns()
    ' 004
    ' Keyboard Shortcut: Ctrl+j     ' must be set on the user's machine

    ' list the sheets on which you want to add columns, CSV format
    Const SheetNames As String = "Data,International Connectivity,Voice"

    Dim Ws      As Worksheet        ' alternating worksheet
    Dim Sn()    As String           ' and array created from 'SheetNames'
    Dim i       As Integer          ' index to the array Sn()

    Sn = Split(SheetNames, ",")
    For i = 0 To UBound(Sn)         ' loop through all sheet names
        Set Ws = ThisWorkbook.Worksheets(Trim(Sn(i)))
        AddColumn Ws                ' send Ws to the procedure 'AddColumn'
    Next i
End Sub

Private Sub AddColumn(Ws As Worksheet)
    ' 004

    Dim Tmp     As Variant          ' for intermediate data storage
    Dim Cl      As Long             ' last used column on Ws

    ' within a 'With' statement the object is specified is
    '   represented by a leading period (twice in the first row below)
    With Ws
        ' find the last used cell in row 2
        '   it's not good practice to keep data to the right of
        '   your data for reasons like this one. I moved your table
        '   one row down. Better move it to another sheet.
        Cl = .Cells(2, .Columns.Count).End(xlToLeft).Column
        .Columns(Cl).Insert Shift:=xlToRight, CopyOrigin:=xlFormatFromLeftOrAbove

        ' attempt to set the correct date
        With .Cells(2, Cl)
            Tmp = .Offset(0, -1).Value      ' pick up the last column's date
            If IsDate(Tmp) Then .Value = Format(DateValue(Tmp) + 1, "d-mmm-yy")
        End With
    End With
End Sub

This code will write the date in the caption if the previous column has one to count from but it won't add the missing borders with which you struggled so much. It's better to copy the borders from the existing column. Therefore, if the copy is wrong the error must be fixed in the original.

As you now know, a cell has a border on each of its four sides. Imagine two vertically adjacent cells. What happens if the bottom border of the top cell is set but the top border of the one below isn't? In the sheet you won't be able to see the difference. But if you select both cells and look at Format Cells > Borders you will see the border between the cells shown dimmed, indicating that they aren't the same.

When column formats are copied Excel (or perhaps VBA) tries to set both overlapping borders identically and, faced with conflicting instructions, decides not to apply any. The solution is to go back to cell formatting and make sure that the overlapping borders are set uniformly. That won't work every time in every case but I think it will work in this case and this time. With an eye on the volume of code needed to set the borders it's worth a try,