You might just want to use a String parameter instead of a Feature Class parameter. It works for me if for the "output feature class" field I do something like %Workspace%\%Name of Feature Class to Create%, where Workspace is a Workspace variable and Name of Feature Class to Create is a String variable.