I think the texture could work, but if you're going to do that you'll need to worry about priority. How busy something is affects positive and negative space, and you'll want a contrast in there somewhere. In other words, if you make the background detailed you'll want the foreground more plain. I think you'd be better off doing some zelda style minimal details, like in ALttP or Minish Cap.