Thanks, Razzomega. The B&W shot is a real improvement: quality is really higher and the aspect ratio is finally accurate. And the soldier with is tongue out too: original shot had black bars. About the bikers and the streets, the improvement is less obvious but noticeable. I'll give it a try too and see if I can do better myself. But if I don't, your updates will do just fine.
Regarding promo shots: if you are absolutely sure the shot is not in the movie, try to get a shot that comes as close possible. Angles can be different, for example, as long as the content of the shot stays the same.
I couldn't find the exactly same frame but this one looks almost the same and then I felt it was alright updating it: Stranger than Paradise Done Old: http://whatthemovie.com/shot/4513
Yes, maybe you can't really see here but three of them had white lines and the others where clearly bad quality and had weird colour and couple of them had replaceplease tags
I think yours looks better... but I'm afraid the original one doesn't break any rule. Just ask the uploader if (s)he agrees that you replace it when it hits the Archive.