Chris,
I've searched the help and can't find where you reference that you should be able to import a featureclass into a recordset.
However - I agree you should be able to do this. Like you said, you can do it in ModelBuilder from ArcMap. Also as a note, I dont think this is an arcpy issue, its probably been like this back since the time of import arcgisscripting (gp.RecordSet)
I just logged the bug - Sorry I cant post the Nim as I'm heading on holidays and dont have time to wait for it to export 🙂 (it is in the system though)
However, as a work around you should be able to do an arcpy.CopyRows(..... "in_memory\table")
And then do your record set from that.
It isn't great, but should keep you moving on your workflow.