Okay, took some time to soak in the code you posted.
First impression: It's a crime against programming.
I bet the graphical problem is that you release the sprite in the destructor, which is called when you erase the enemy from the queued vector. However, the copy in the enemies vector has a copy of the pointer, and therefore points to the memory you just kersploded!
Store pointers in the vectors, not the objects themselves. But don't use naked pointers, use a smart pointer like the shared_ptr from Boost.org. Or the TR1 smart pointer (whatever it's called), if you like it better for some reason.
The shared_ptr keeps track of how many pointers are referencing it and when the last pointer is gone, it calls the destructor of whatever it points to. This is handy because you don't have to worry about the messy destructor problem with the sprite data, but it still cleans up after itself when you .erase() it.
Use .at() instead of , .at() does bounds-checking.
Check out iter_swap()
It calls one copy constructor and two operator= assignments.
That ought to be cheaper than calling .erase(), ~Enemy(), Enemy(), and push_back()
At least, I think so.
Edit: Also, don't use for (int i ...) loops with vectors, use iterators in the form of:
for (std::vector<Enemy>::iterator i = enemies.begin(); i != enemies.end(); i++)
Just be careful about using .erase() in it. If you use .erase(), do it like this:
for (std::vector<Enemy>::iterator i = enemies.begin(); i != enemies.end();)
i = enemies.erase(i);
Note that, when using this form, you don't need to check the size of the vector, because if it is 0, i will be equal to enemies.end() and will bail out immediately.
Phew. How come I've been helping people all day, but my ONE topic has 2 replies, one of which is from me?