I've been working on a game engine for about a year now, but I still feel like my solution to layer/depth management isn't elegant or robust enough.

Currently, I have the game set up a bunch of layers when it starts, which are essentially just strings representing the layer name- "sprites0", "sprites1", "bg0", "bg1", etc. These strings are mapped to lists of the objects that are on each layer.
When objects are added to the game world, you specify a layer for them to go on, and the object gets added to the corresponding layer's list of objects.

The advantages of this method are that I don't have to sort the objects (because I know the layer order), it's easy to keep different types of objects separate (e.g. players and enemies always go above the background, because the layer "actors" is above the layer "bg"), and it's easy to retrieve all objects on a layer (just get the list associated with the layer name).

The disadvantages are that adding objects is slightly slower (hashtable lookup for the layer name/list), changing an object's layer is difficult, and objects don't know what layer they're on.

Are there any other ways that anybody recommends to manage layers or object depth, or any recommended solutions to mitigate these disadvantages?

Don't forget the advice of "write games, not engines"

Ha, I knew that would come up. I lurk a lot here, and see that often enough!
I am writing multiple games, and the engine is a collection of stuff that they all need and use together. Would that be more of a "common framework" than an "engine?" I'm not sure about the difference, but it is what it is!

Is it too slow for your game(s)? That is to say, is it actually causing a problem or is this just a concern that it could possibly be faster?

More the latter than the former. None of my games take FPS hits because of it, but it could be faster.

Why? There's nothing about the design you described that means it should be -- what makes changing an object's layer difficult, and is it something you actually need to do often?

Well, I've got another hashtable of object names/layer names that I can use to look up an object's layer. I look it up and get the name of the layer it's on, look up the layer in the hashtable of layers, remove the object from that layer's list of objects, look up the layer to move the object to, and add it to the second layer's list of objects. That's a lot of looking stuff up, and if I ever want to do some sort of complex, depth-related effect (faux 3D, complex particle system, etc.), I'm sure it would chug along. It would almost certainly need to be a faster process to have decent FPS during such an effect.
The reason I'm looking at the layer system now is that I don't want to sandbox myself into avoiding such effects in the future.

Do they need to? Why?

If I'm ever doing a complex effect (like above), there would be logic associated with layers, and the objects themselves might need to know. I could look them up in the hashtable, but again it's going to be slow for things like particle systems.