I am now calculating the normal to the surface by finding the velocity of the contact point and then normalizing that velocity. This does seem to give me the normal for that surface of contact. Is this right?
No. The normal doesn't depend on the velocities etc of the colliding shapes, just their shapes.
Also - you're not looking for the "surface normal" - a property of just on of the contacting surfaces. You need to contact normal, which is a property of both surfaces.
You need to explain in more detail what you're trying to do. Giving a complete answer for the 3D case will be a waste of time and largely irrelevant if you're just concerning yourself with circles in 2D. However, the general result is: the contact normal you're looking for is the direction of the reaction forces in the case of zero friction (yes, that only helps when you know the answer... but by imagining what would happen in the zero friction case you might be able to work out what the normal must be).
For some contacts this is trivial - e.g. for a sphere/circle it will always be in the radial direction. For a contact with a face in 3D (whether a box or part of a triangle mesh etc) it will always be normal to the face. For an edge in 2D it will always be normal to the edge (you can think of a circle being made up of an infinite number of edges).
Basically in 2D, where you only have edges and corners, you need to consider only edge-corner contacts, which are trivial. You can ignore corner-corner contacts, and edge-edge contacts can be converted to two edge-corner contacts.
In 3D you have to deal with faces, edges and corners. Anything contacting a face results in the face's normal. If two edges contact take the cross product of the edges. Ignore corner-corner and corner-edge contacts.
If you already have the shapes penetrating, then a reasonable option is to take the direction that minimises the overlap/penetration distance.