Sorry, a little late to this conversation. Could there be a package libopencv-nonfree-dev by any chance ?
SIFT and SURF are indeed patented, but there have been no patent disputes so far. Also there are a lot of other free invariant features detectors / descriptors that one can use if patents become a real issue. For now it is just convenient to use Sift as it works well in most cases. Cheers, Matthieu
