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}

See [here][1] for the purpose of `Block` around `Needs`.

----

P.S. It turns out that the ``GraphUtilities`ToCombinatoricaGraph`` function re-adds Combinatorica to the context path every time it's called. If you prefer not to have Combinatorica in the context path, you can consider editing GraphUtilities.m and changing ``Needs["Combinatorica`"]`` to ``Block[{$ContextPath}, Needs["Combinatorica`"]]``.


  [1]: http://mathematica.stackexchange.com/q/5563/12