Comment # 2 on bug 983173 from Wolfgang Bauer

(In reply to Wolfgang Bauer from comment #1)
> Try to remove ~/.kde4/share/config/kmahjonggrc and ~/.config/kmahjonggrc and
> it should work.

Or open ~/.config/kmahjonggrc in a text editor and adjust the file paths
accordingly.
I.e. replace:
Background_file=/usr/share/kde4/apps/kmahjongglib/backgrounds/default.desktop
with:
Background_file=/usr/share/kmahjongglib/backgrounds/default.desktop

And so on...