Apologies for the (big) bump everyone. I just wanted to mention that atrembla's instructions (then ahmad2080's correction) has done wonders for getting my recovery partition up and running again.
I, like many other people these days, have an OEM laptop without any installation or recovery media...