need help with correcting the background

[Blighty]

How about replacing the background? Like this:
http://imgur.com/a/6RV0g

What I did:
1. Selected the elephant using the foreground select tool
2. Inverted the selection
3. Deleted the background
4. Created a new transparent layer below the elephant
5. Filled this new layer with grey using a gradient