Por lo que entiendo, tu tabla uf tiene la geometría de las unidades federales y la geometría de los municipios, y no tienes ningún problema con los polígonos (usualmente cuando haces este tipo de cosas, las geometrías no son perfectamente similares y hay aproximaciones que hacen que la correspondencia entre 2 tablas sea difícil, pero aquí asumo que vienen de la misma fuente o han sido limpiadas previamente con algo como un snaptogrid y otras).
En este caso, estás seguro de que tus municipios están completamente dentro de tus unidades, así que no veo ninguna razón por la que la solicitud que hiciste no funcione. El st_intersects no es necesario sin embargo. Para hacerlo más claro, lo escribiría de esta manera:
SELECT uf.gid, ST_Union(geom)
FROM (
SELECT uf.gid, m.geom FROM municipios as m LEFT JOIN uf ON st_contains(uf.geom, m.geom)
) as req
GROUP BY uf.gid
Si tienes problemas con geometrías que no deberían estar aquí, ¿quizás nos puedes dar un ejemplo?
Y en caso de que tus geometrías no sean de las mismas fuentes y no estén perfectamente alineadas, tendrás casos en los que el municipio puede estar ligeramente fuera de la unidad federal, así que en lugar de st_contain necesitarías usar st_intersection con todas las unidades federales (donde st_intersect), ordenarlas por st_area y tomar la primera, para obtener la unidad federal donde el municipio está más presente, ¡así que es una historia diferente...