Rebuild the sky with a couple of colour fill layers, one darker, one lighter, and a gradient to blend the tonality from darker to lighter to keep it natural-looking. You can select also the exact shade of blue you want on each layer. It's a lot easier than trying to mess with low-data JPEGs. To resave as a JPEG you will need to flatten it, so keep one copy as a TIFF, with the layers intact for future adjustments should the need arise.