Is it possible to use SYB to transform the type?

Question

I want to write a rename function to replace String names (which represent hierarchical identifiers) in my AST with GUID names (integers) from a symbol table carried as hidden state in a Renamer monad.

I have an AST a type that is parameterized over the type of name. Names in the leaves of the AST are of type Name a:

data Name a = Name a

Which makes it easy to target them with a SYB transformer.

The parser is typed (ignoring the possibility of error for brevity):

parse :: String -> AST String

and I want the rename function to be typed:

rename :: AST String -> Renamer (AST GUID)

Is it possible to use SYB to transform all Name String's into Name GUID's with a transformer:

resolveName :: Name String -> Renamer (Name GUID)

and all other values from c String to c GUID by transforming their children, and pasting them back together with the same constructor, albeit with a different type parameter?

The everywhereM function is close to what I want, but it can only transform c a -> m (c a) and not c a -> m (c b).

My fallback solution (other than writing the boiler-plate by hand) is to remove the type parameter from AST, and define Name like this:

data Name = StrName String
          | GuidName GUID

so that the rename would be typed:

rename :: AST -> Renamer AST

making it work with everywhereM. However, this would leave the possibility that an AST could still hold StrName's after being renamed. I wanted to use the type system to formally capture the fact that a renamed AST can only hold GUID names.