Olduvai
Dear Sarah
Peanut
Gryphius
Greymantle

Alternately use these hand filters to weather any font...

http://www.misterretro.com/image_filters.html

I have used ITC Tempus in place of Papyrus a few times

http://www.myfonts.com/search?search%5Btext%5D=tempus

Not all of these are textured in the same way as Papyrus, but here are some rough serifs akin to the Old Claude and MVB Celestia Antiqua you mentioned:
Garamond Rough
MVB Gryphius
ITC Founders Caslon
Linotype Compendio
Grit Primer
FF Irregular
ITC Old Times
Marco Polo

@paul: oh i really like MVB Greymantle thanks!
@sii: Do you reccomend one set of filters over the others so that i don't have to buy 3?
@guerella: ahh tempus is nice but it is a bit too light for me i think.
@stephen: Thanks some great fonts there. btw is there a name for these types of textured fonts? (just so i don't have to refer to papyrus lol)

Weathered, antiqued, worn, rough, textured.

Here's FontShop's Photoshop tip for creating a weathered affect. Could modify it for your use.

Another: Frances Uncial

cool thanks stephen!