Let me tell you how I change it, since I do it pretty often. If you’ve already added a photo to your Story, tap the three dots at the top, choose Draw, select the colour you want, and then press and hold anywhere on the background. It should fill the background with that colour. If you just want a plain coloured background without a photo, use the Create (Aa) option in Stories and choose the background colour from there.