Well, it may be legal to create such a painting, but (depending on details) it may be a derivative work, in which case the original work's copyright still applies.
In other words, in your example, the painter is not necessarily free to distribute their painting while ignoring the original image's copyright.