Setting translucent to YES on the navigation bar does the trick, due to a behavior discussed in the UINavigationBar documentation. I'll report here the relevant fragment:
If you set this property to YES on a navigation bar with an opaque custom background image, the navigation bar will apply a system opacity less than 1.0 to the image.
Something I stumbled upon is that if I created a subclassed UINavigationBar and then created an empty -(void)drawRect: method, I would get a transparent navigation bar. I only tested this in iOS 7.*, but it seemed to work!