Se houver um pacote genérico sem versão em que você possa confiar (como no caso Java: java-runtime vs., por exemplo, java6-runtime ), dependa disso. Se não houver, você precisa criar pacotes especializados para as diferentes versões do Ubuntu. Veja o pacote que você depende do arquivo control e veja se Provides algo mais genérico no qual você pode confiar.