The VB Picturebox will only Save Modified Images as Bitmap files, to Save as an Icon the Picture needs to have been Assigned an Icon Image, to do this, use the ImageList Control, which has an ExtractIcon Method, ie.
Code:
'Add a Picturebox, ImageList and Command Button to a Form..
Private Sub Command1_Click()
    With ImageList1
        .ListImages.Add , "NewIcon", Picture1
        'Set the transparent Color of the Icon
        .MaskColor = vbButtonFace
        'ReAssign the Icon to the Picturebox,
        'It'll now save it as an Icon as it's in an Icon Format
        Picture1 = .ListImages("NewIcon").ExtractIcon
        'Remove the Image from the ImageList
        .ListImages.Remove "NewIcon"
        'Save the Icon
        SavePicture Picture1, "C:\NewIcon.ico"
    End With
End Sub