Você está correto em assumir que os patches precisam ser aplicados ao código-fonte, não ao pacote compilado que está instalado no sistema. Isso ocorre porque o arquivo .patch contém informações sobre diferenças nos arquivos de código-fonte. A versão compilada do programa está em forma binária e é imutável.
Lembre-se de que apt tem uma ferramenta útil para a criação automática de pacotes a partir do código-fonte, apt-source .