This was confirmed by support to be a bug.

One workaround is to use ``Combinatorica`VertexConnectivity``:

    graph1 = CycleGraph[8];
    graph2 = UndirectedGraph[
       Graph[{1 -> 3, 1 -> 7, 1 -> 10, 2 -> 5, 2 -> 6, 3 -> 6, 3 -> 10, 
         4 -> 7, 4 -> 8, 4 -> 9, 5 -> 9, 6 -> 10, 7 -> 8, 8 -> 9}]];
    
    Block[{$ContextPath},
     Needs["Combinatorica`"];
     Needs["GraphUtilities`"]
     ]
    
    Combinatorica`VertexConnectivity@
       GraphUtilities`ToCombinatoricaGraph[#] & /@ {graph1, graph2}