Clear the "Do not ask again" dialog in Gallery when changing Wallpapers
The problem was a silly one. When you try to select a wallpaper you're given two choices: full wallpaper for the virtual desktop (option 1, scrollable wallpapers) and a fixed wallpaper (the second option).

If you select the second option, it will ask if you want to use the same wallpaper for the lock screen.

However, if you select the first one, it won't ask you anything (because it can't be set) — ths was the root of the problem.

I'm assuming that, if you do tap the "Do not show this dialog again" can be reset by tapping "Clear defaults" in the Gallery App.