When you declare a type signature such as
f :: C x => a -> b
there is an implicit "forall":
f :: forall x. C x => a -> x
That is, the type signature must hold for all x such that C x holds. However, in your case, it only holds for String – while A String does hold, that is irrelevant, because the type signature states that it must hold for *any* x such that A x that the caller wants. To put it another way, the caller decides the "b" in that type signature, not the function implementation.
What you want is something like
f :: exists x. C x => a -> x
so that f will return some unknown value such that you know it is an instance of C x.
Hope that helps,
Andrew