Although I could see how the sharp edges of the tiles might be interpreted as non-background pixels. So I still wonder if blurring the background might be worth trying.
I suspect tile edges are less of a problem. The tiling is simple, consistent and pervasive, so the player should quick learn what is background when observing lemmings falling out of entrances and seeing where they land. But perhaps the background could be made slightly darker still to further distinguish from some of the darker colors used in terrain, particularly if there are darker terrain pixels that can become exposed through typical removal of terrain during the course of playing the level (maybe less the case for the level shown in the screenshot).
my background was barely visible and namida's I couldn't see at all. But on my regular PC they look much better.
I actually had to look very close to see the backgrounds on namida's screenshots even on my laptop. But I think that's partly because those screenshots are not enlarged to the full size of the screen like they would in actual play.
Backgrounds are tricky: the pixel nature of the game mechanics plus many terrain pieces being irregularly edged (as opposed to blocky straight edges) greatly increase the potential for confusing what is background and what isn't. At least I feel that may be the case when I study and compare how, say, Lemmings 3 handles background graphics.