We've recently converted several of our websites to require HTTPS on all pages. HSTS headers have been set and rules added into Apache to 301 redirect all traffic from HTTP to HTTPS.
However, similar to this question, we still have plenty of URLs from the old HTTP version of the website reported in Google Webmaster Tools as the "Linked from" source of 404s in the HTTPS version. This means search engines are trying to load URLs on HTTP and are being redirected to a 404 page on HTTPS.
It seems correct to redirect all traffic from HTTP to HTTPS, but from another perspective feels odd to be redirecting to 404s. I could try to reconfigure things so that non-existent URLs return a 404 on HTTP and stay there whilst redirecting valid requests to HTTPS, but it really doesn't seem either practical or secure.
Is this correct, or should I be doing something different to avoid redirecting to 404s? Should I even worry about this? Are there other SEO implications to consider?