uuid_generate

Попробуй:

$ldd твой_бинарик

Должен выдать список либ, от которых зависит твой_бинарик. Если одна
из зависимостей не будет найдена - все напишут на экране. Думаю что
у тебя что-то с кэшем для ld.so. Более подробно - man ld, man ldd,
man ld.so.

военный! -luuid будет искать сначала в путях линковки libuuid.a(в некоторых случаях потом libuuid.so)
нужен этот флаг для того чтобы не писать lib и .a и не знать путь.
поэтому линкуй так:
gcc -c prog.c
gcc -o prog prog.o /lib/libuuid.so.1.2

Всем спасибо, но:
$ldd мой_бинарник сделать не могу, т.к. бинарник не генерится в результате ошибки линковки.
Делая
gcc -c prog.c
gcc -o prog prog.o /lib/libuuid.so.1.2
или
gcc -c prog.c
gcc -o prog prog.o /usr/lib/libuuid.a
дает ту же самую ошибку линковки, что и при нормальной компиляции с параметром -luuid.

Сделал я ld /lib/libuuid.1.2, и возвернуло ошибку cannot find entry symbol _start; not setting start address - похоже именно поэтому не линкуется. Попробую переустановить библиотеки.

Всем большое спасибо.

Да чойто я сбойнул ;)

А вот, собственно и решение проблемы.
Как известно, когда исходники - файлы *.cpp, gcc вызывает g++ для компилирования кода. В общем, в моем случае, это были именно cpp. В файле же <uuid/uuid.h>, в том месте, где декларируются функции, нет директивы
#ifdef __cplusplus
extern "C" {
#endif
...
#ifdef __cplusplus
}
#endif
Как по мне, так это очень грубая ошибка.
Таким образом, компилятор С++ генерирует вызов функции uuid_generate как вызов любой функции С++, а не С. А линковщик, естессна, не находит ее, т.к. она скомпилирована в libuuid.a(.so) как функция С.
Выход:
#ifdef __cplusplus
extern "C" {
#endif

#include <uuid/uuid.h>

#ifdef __cplusplus
}
#endif