but GHC complains:
Illegal instance declaration for `Foo (Either b b)' (The instance type must be of form (T a b c) where T is not a synonym, and a,b,c are distinct type variables) In the instance declaration for `Foo (Either b b)'
unless I'm totally mistaken, your problem isn't the distinction thingy, but rather an error like supplying an Int for where you need (Int -> Int -> Int). That is, you're trying make (Either String String) an instance of Foo, (Either String String) already being a fully constructed type; Foo, on the other hand, seems to require a type constructor that is yet to parameterize over three more types (e.g. StateT).
I think that you are mistaken. The OP listed:
class Foo a instance Foo (Either b b)
Without further information, Haskell compilers will assume that the type(s) in a class declaration has/have kind * (Report section 4.6). Either b b does have kind *, so that's not the problem.