http://code.google.com/p/osd-lyrics/

I used to have lrcshow-x, but it seems to be hard to install and do not cache lyrics locally. From the osdlyrics download file list, use the 0.4.0 version for Ubuntu 10.04 (Lucid). Newer versions are broken in MPRIS2 protocol handling, see here.