ross what does your sources.list show. Find it in look like. Open to edit with gedit or your text editor. I just edit it with the sudo nano /etc/apt/sources.list. If you do it that way then close it with Ctrl C then finish with y to save.
I only got one in my sources.list
Code:
deb http://http.kali.org/kali kali-rolling main non-free contrib
not to freak you I already removed the top two for the
cd
Then try it all over again. I'm teling ya it needs to regenerate the keys. If not then yes u may have a bad install. But mine was the same issue and it never would generate anything until I put that link into the sources.list.