You can also get the "No public key" error if you have imported an old version of the Tails signing key.
gpg --check-sigs A490D0F4D311A4153E2BB7CADBB802B258ACD84F
pub 4096R/58ACD84F 2015-01-18 [expired: 2017-01-11]
uid [ expired] Tails developers (offline long-term identity key) <[email protected]>
sig!3 58ACD84F 2015-01-18 Tails developers (offline long-term identity key) <[email protected]>
sig! BE2CD9C1 2015-01-19 Tails developers (signing key) <[email protected]>
sig!3 58ACD84F 2015-09-27 Tails developers (offline long-term identity key) <[email protected]>
uid [ expired] Tails developers <[email protected]>
sig!3 58ACD84F 2015-09-27 Tails developers (offline long-term identity key) <[email protected]>
The Tails signing key I imported last time expired on 2017-01-11.
After I downloaded the new signing key the result is different:
gpg --check-sigs A490D0F4D311A4153E2BB7CADBB802B258ACD84F
pub 4096R/58ACD84F 2015-01-18 [expires: 2018-01-11]
uid [ unknown] Tails developers (offline long-term identity key) <[email protected]>
sig!3 58ACD84F 2015-01-18 Tails developers (offline long-term identity key) <[email protected]>
sig! BE2CD9C1 2015-01-19 Tails developers (signing key) <[email protected]>
sig!3 58ACD84F 2015-09-27 Tails developers (offline long-term identity key) <[email protected]>
sig!3 58ACD84F 2016-08-30 Tails developers (offline long-term identity key) <[email protected]>
uid [ unknown] Tails developers <[email protected]>
sig!3 58ACD84F 2015-09-27 Tails developers (offline long-term identity key) <[email protected]>
sig!3 58ACD84F 2016-08-30 Tails developers (offline long-term identity key) <[email protected]>
sub 4096R/752A3DB6 2015-01-18 [expires: 2018-01-11]
sig! 58ACD84F 2015-09-27 Tails developers (offline long-term identity key) <[email protected]>
sig! 58ACD84F 2016-08-30 Tails developers (offline long-term identity key) <[email protected]>
sub 4096R/2F699C56 2015-01-18 [expires: 2018-01-11]
sig! 58ACD84F 2015-09-27 Tails developers (offline long-term identity key) <[email protected]>
sig! 58ACD84F 2016-08-30 Tails developers (offline long-term identity key) <[email protected]>
sub 4096R/A0EDAA41 2016-08-30 [expires: 2018-01-11]
sig! 58ACD84F 2016-08-30 Tails developers (offline long-term identity key) <[email protected]>
The new key expires in 2018-01-11. Now when I verify the signature I see "Good signature".