Coraline has the flexible header image feature which means you can upload any size header you wish.
That's not correct. The table on the doc TSP linked to lists the themes that support a header image, not the themes that support a so-called flexible header image.
Coraline header image dimensions are 990 × 180 pixels in the two column layout.
That's not correct either. No matter what the layout, the image you upload will be used as is if it's 990×180, or will be cropped to these dimensions if in a different aspect ratio. What size will actually show up depends on the layout you have selected in Appearance > Theme Options.
I have no idea what version of Coraline I have.
The layout you're using is: content left, single sidebar right. Total width in this case is 770px, so your header image is downsized to fit: original 833x600, displayed version 770x555.
Yet somehow I uploaded a header image of 833 x 600 pixels last year.
On WP, last year is long time ago. The key is raincoaster's "in the past": WP changes and updates things all the time. Even the CSS of the theme has changed, so presumably its PHP has changed as well, and handling images in general has also changed. The CSS of the theme did and does allow variable height (hence the display of your current header image), but your dashboard no longer allows this.