Shai - 11:36 am on Oct 23, 2013 (gmt 0)
This is very strange. I just checked two penalty removal clients and both have the penalty message on both the www and non-www. In both cases, the vast majority of links were to one or the other. One client that had his penalty revoked a couple of days ago, has had both instances of the message disappear (www and non-www). This insinuates that Google does not differentiate between the two for penalty purposes. Your case is definitely out of the ordinary.
If I were you, I would just fill out a RR on the non-www site explaining the discrepancy. I almost guarantee you that you will get a penalty-revoked message on that one as well within 8 or 9 days. I would also mention that rankings have not improved at all, sometimes, that can cause them to nudge it a little. ;)
Please keep us informed on how you get on.