Here is an example that worked for me: Tweak your paths as necessary. The trick is that you have to write out a blank file first.
see: http://www.codeproject.com/Tips/257193/Easily-zip-unzip-files-using-Windows-Shell32
Dim sc As New Shell32.Shell()
Dim startBuffer() As Byte = {80, 75, 5, 6, 0, 0, 0, 0, 0, 0, 0, _
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
' Data for an empty zip file .
FileIO.FileSystem.WriteAllBytes("C:\backup.zip", startBuffer, False)
Dim input As Shell32.Folder = sc.NameSpace("C:\temp")
Dim output As Shell32.Folder = sc.NameSpace("C:\backup.zip")
output.CopyHere(input.Items, 4)