new Graph in Mathematica 8.0

The new Graph objects are atomic in Mathematica 8. Thus, like strings or images they do not have internal structure that can be manipulated in the normal fashion. What is particularly unusual is that the new objects have a FullForm that looks like it can be manipulated symbolically. But appearances can be deceiving -- not only is that representation inaccessible to pattern-matching, but it is not even a valid graph specification if you feed it back to Mathematica using copy-and-paste.

I found a couple of hacks that can be used to manipulate graph structure. The first tries to use the "official" channels to extract the properties of graphs:

adjustedGraph[g_, newOptions___] :=
  Graph[
    VertexList@g,
    EdgeList@g,
    newOptions,
    Sequence@@Table[p -> PropertyValue[g, p], {p, PropertyList[g]}]
  ]

You can use this function like this:

g = GridGraph[{4, 4}, GraphStyle -> "DiagramBlack", ImageSize -> Tiny]
adjustedGraph[g, GraphStyle -> "BasicGold"]

This function uses VertexList, EdgeList and PropertyValue to extract the graph properties. Unfortunately, some options are not recoverable by this means. For example, the Graphics option ImageSize will be lost using this method.

An even more heinous hack exploits the pseudo-symbolic representation of FullForm:

adjustedGraph2[g_, newOptions___] :=
  "Hold@" ~~ ToString[g, InputForm] //
  ToExpression //
  #[[1, 3]] & //
  Graph[VertexList@g, EdgeList@g, newOptions, Sequence @@ #] &

Despite its evil nature, this second function performs more satisfactorily as it appears to retain most graph options. I say "most", because I have not yet experimented with more esoteric options like wrappers, shape functions and graph properties assigned after the fact. There are no guarantees that this method will work unchanged as Wolfram changes the representation of graph objects (or even that it works for all possible graph definitions now).

There ought to be a way to achieve this without hacks. I still hold out hope that there is some function lurking out there that will give the complete symbolic representation of a graph object.

As for the symbol conflicts that arise after loading the Combinatorica package, you can still access the original symbols by explicitly specifying the package name, e.g. System`CompleteGraph. If you prefer to have the system symbols take precedence over the Combinatorica symbols, you could evaluate the following expression to change the package search order:

$ContextPath =
  $ContextPath /.
    {x___, c : "Combinatorica`", y___, s:"System`", z___} :> {x, y, s, c, z}

I note that Wolfram is effectively deprecating the Combinatorica package by issuing a scary warning message when you load the package.

The following will preserve the vertex coordinates of the original graph.

g = CompleteGraph[5];
coords = PropertyValue[{g, #}, VertexCoordinates] & /@ VertexList[g];
Graph[VertexList[g], EdgeList[g], GraphStyle -> "BasicGold", 
 VertexCoordinates -> coords]

I would think something similar could preserve other options as well, though I haven't tried it.

For #2, you should be able use distinguish between the two using the context. Thus, System`CompleteGraph[5] creates a new V8 graph, while Combinatorica`CompleteGraph[5] creates an old Combinatorica graph.

I'm not sure exactly what you mean in #1, but you can convert the Graph to Graphics, then the contextual menu will appear as before. I'm not so sure that this is an improvement, though.