Thanks to Mark Round, the problem is solved. I just have to symlink /usr/local/lib/libreadline.so.5 to /usr/local/lib/libreadline.so.4 and it all seems to work.
Um, thanks - but this isn't what I suggested doing :)
While symlinking libraries for backwards compatibility reasons may work in the short term, it can open up a whole can of worms later on. It seems as though your version of PostgreSQL is linked to an older version of readline - the best option would be either to downgrade your version of readline (assuming nothing else on your system is making use of it), or obtain / build PostgreSQL linked to a newer version of readline.