This is a constant problem for us too (on our new Leopard only machines), any program that uses the OS to display PDFs will keep dropping type.
This means the finder, preview, keynote and mail applications. Our placed PDFs in keynote slides don't show type. In finder windows, the type in pdfs (the icon) is sporadic at best, in mail and entourage the type on pdfs in email is also sporadic. Preview itself is completely hot or miss. But open the same pdf in acrobat and viola, perfect.
Clearing the font caches and restarting is only a temporary fix.
This is an inexcusable bug that makes doing professional design work (the sole reason we have macs) extremely difficult. I wish we had not upgraded any of our computers.