package verify is run before package add, causes always error when package is not (yet) installed. aptitude does not return error on non-existant package, use apt-get instead.
(cherry picked from commit 77a1934647b6cd45928f07f04215ea2dfd2cfc08)