Ну я наверное не буду оригинальным, но первый же ответ от Google скорее всего тебе поможет
"sudo apt-get install libboost-regex1.49.0"
"sudo apt-get install libboost1.49-dev"
"sudo apt-get install libboost-regex1.49-dev"
Так сказать, цело ассорти вариантов.
а разве libboost-all-dev не ставит все обновлённые пакеты либы?
49 кстати в репах нету(
ау, кто сталкивался с руганью Клэймора на 49 версию ?