Have you thought about how much extra overhead there is in storing the checkins using MongoDB's BSON structures? Considering how often you do this, you might consider packing a specialized version of a user's history (at least for this purpose -- sort of a denormalization) into a array of 64-bit placeIDs? This means a checkin would only occupy 8 bytes of space and there would be no overhead. 1 billion checkins = 8GB of data. You could even keep these in memcached and use a sort of write-through strategy.

EDIT: I thought about this a bit more, and the checkins are probably time-sensitive, so another 32-bit timestamp (Foursquare Epoch) would need to be stored for each checkin.