I was thinking about doing primecoin a while back.  It has a different POW than other coins that I have done, and that would be a challenge.

Unfortunately, I don't have time to work on it.