“Most black holes are formed when stars collapse,” Ivy said. 
     “But there’s a theory that some of them were created shortly 
     after the Big Bang. The universe was lumpy. Some of the lumps 
     might have been dense enough to undergo gravitational 
     collapse. They could form black holes that instead of 
     weighing what a star weighs could be a lot smaller.”
     “How small?”
     “I don’t think there’s a lower limit.”

Yes there is. Black holes lose mass by Hawking radiation: http://en.wikipedia.org/wiki/Hawking_radiation

A black hole smaller than 0.8% Earth masses loses more mass than it gains from the cosmic microwave background, and will eventually evaporate.