May be this should be added to some FAQ or troubleshooting in README.linux
Under Debian 6 I had to update boost libs to 1.46, install libavcodec-dev to satisfy libavformat-dev and set LIBS manually
make ‘LIBS=-lboost_system -lboost_filesystem -lboost_thread -lboost_iostreams -lz -lavcodec -lavutil’
t know how mach of this originate from messy setup on my box, but it took me about an hour to find this out before make succeeded. I hope this will save someones time in future.