Just a little something to add, this is not a "bad smell" at all... in fact, recursive (including mutually recursive) data types are the bread and butter of Haskell (and functional languages in general).  For example:

data BinTree a = Empty | Branch a (BinTree a) (BinTree a)

This says that a binary tree containing 'a's is either Empty, or a Branch consisting of an 'a' and two binary trees.  This isn't stinky, it's quite elegant.  Your Scenario and Step data types look just peachy from an idiomatic point of view; the solution (as others have pointed out) is to use data declarations rather than type synonyms.

-Brent