Same problem, even with new-style classes. Here, I'll show the function
I use to generate the graph as well.

class Vertex(object):
	def __init__(self, type):
		self.type = type
		self.color=-1
		self.edges=[]
		

		
class Edge(object):
	def __init__(self, V1, V2):
		self.vertexes=[V1, V2]
		V1.edges.append(self)
		V2.edges.append(self)

def generate(graph={'V':[], 'E':[]}, seed=777, vertexes=5, edges=25):
	#generates a graph similar to the KEGG pathway database format.
	# Purpose is for testing algorithms on a smaller scale "predicatible" graph
	# For that reason, the "random" selections are seeded with a known
number. This is to be able
	# to measure efficacy, in that on the same graph, if algorithm A
performs in half the time, its 
	# not a characteristic of the graph, but the algorithm.
	r=random.Random(seed)
	p=[0, 0, 0, 0]
	c=0
	#generate vertices, with a regularly incremented set of numbers, to
appear like the KEGG pathway database does.
	while c!=vertexes:
		#This is ugly, could be done easier in a loop. Fix later.
		p[3]+=1
		if p[3]>9:
			p[3]=0
			p[2]+=1
		if p[2]>9:
			p[2]=0
			p[1]+=1
		if p[1]>9:
			p[1]=0
			p[0]+=1
		#we copy the set of numbers, due to the way python passes lists by
reference, instead of by copy.
		v=Vertex(p[:])
		graph['V'].append(v)
		c+=1
	
	
	v=graph['V']
	if len(v)!=vertexes:
		print "Not enough vertices, aborting."
		return graph
	c=0
	#randomly choose two vertices. Could even, randomly, be the same vertex.
	# Then, connect an edge between them. Just creating the edge by
implication,
	# with the vertices passed, connects them all together.
	while c!=edges:
		v1=r.choice(v)
		v2=r.choice(v)
		graph['E'].append(Edge(v1, v2))
		c+=1
	
	if len(graph['E']) !=edges:
		print "Not enough edges, aborting."
	return graph

And here is how I use it:

>>>import graph, copy
>>>g=graph.generate(vertexes=100, edges=500)
>>>g2=copy.deepcopy(g)

Thanks for the prompt response, this isn't critical in nature, just
playing around with the graph, and wanted to alter a copy of it. Ran
into this bug, thought I should report it. :)

-Zeroth