Yeah, that didn't fix the issue. :-( I can run through all of the suggestions listed on the forums, but (a.) I can upload fine on 3.4.x and (b.) the uploads do actually go through, they just error out in the actual upload process and/or in the case of trying to change my header, I get the Not Found when trying to pick an image already uploaded and when I upload through the header screen it gives me a Not Found after the cropping screen. In both cases the header image does not change.
EDIT: To clarify, previously I was getting a Not Found on the actual Upload Media screen as well as the issues with the header image.