Schneier-based ideas work for me

I chose to use an app not mentioned here - Debian/Ubuntu have a package called pwsafe (not to be confused with the iOS app mentioned here!), which uses version 1.x/2.x password safe databases of the Schneier school.

It's command-line only, which suits me.
(See http://packages.ubuntu.com/lucid/pwsafe for package details.)

I did install Password Gorilla as well, but that's mostly just for editing - in case I add or remove something to the wrong category, for example. Most password retrieval I do from the CLI, and most adding too.
(Set up an export on login to point to the password database you use by defauly, and it becomes super-easy!)

I did consider the fancy all-singing all-dancing cloud solutions, but none seemed to support Linux very well.

And frankly, how hard is it to sync one file via Dropbox/Ubuntu One/SpiderOak/$YourPoison?

That the file format is well understood and can be read on most platforms was really my main concern. Finding Passwd Safe on Android was the icing on the cake - now I have access to my password safe on my phone if I need it, which is great.
(Especially as I use the Ubuntu One Files app to grab the safe database file itself.)

Pretty interfaces and functionality are nice. As a Gnome user, I do of course use Seahorse/Gnome Keyring to record some passwords for applications. But that's a convenience, not my "primary place of record".

Whatever you choose, make sure you can access it from wherever you need to. Being able to access something via a bad interface when you need it trumps not being able to access it at all...