LJ Random or Recent plugin has been tested and updated to work with WordPress 2.8.1 Beta 2.
On a side note upgrading wordpress was as easy as unzipping the latest copy over the existing install. Just make sure you backup your files and database first :-).
Check it out LJ Random Or Recent