I should think the Polulu would work just fine - the total consumption with BT and uSD running is about 250mA - I might even consider it as a cheap alternative to recom.
You could probably also just hook a UBEC to the recom pads, if it came down to that.