There is a discussion about this on r-sig-geo. For a definitive answer you should ask there, cause there are peoples which know the insights of spatial R.
But, you can also do this in GIS desktop applications (export the shape using writeOGR command from rgdal or writePolyShape() from maptools) like QuantumGIS, GRASS or SAGA.
For QuantumGIS use Vector / Geometry Tools / Simplify geometries (I have tested and does not preserve the topology, but applied to Romania admin1 shapefile, looks fine with 2000 nodes).
For GRASS use v.generalize (read the manual for info about the algorithms, there are some).
For SAGA you must first convert the polygon to line (Shapes - Lines / Convert Polygons to Lines), then simplify lines (Shapes Lines / Line Simplification), and finally convert lines to polygons (Shapes - Polygons / Convert Lines to Polygons). I have tested this and the results has the topology preserved.
Cheers and good luck,
gSimplify()has an optional parametertopologyPreservewhich defaults toFALSE. Have you tried setting that toTRUE? – krlmlr Jan 22 at 16:34