The background was painted by hand using some brushes from brusheezy and some standard photoshop brushes.

On a new layer, I traced around the shadow of the original model, flood filled it with dark brown and blurred it slightly.

Cut out the model and paste on new layer. Adjust colors with levels and saturation. Use the dry brush filter to give an artistic painted effect.
I used this layer as the color sample layer to do some finger painting on the next layers.
On the layers section you can see some lighter versions of the background. That's because the original colors I used were a lot lighter and I duplicated and multiplied them a few times because they looked too light behind the model.

On a new layer, using the smudge brush with finger painting and all layers checked, I traced the outline of the model from the previous layer.

I put the brush settings on this picture so you can see I used the fan brush on normal mode, 45 percent, sample all layers checked, finger painting checked.
When you use sample all layers and finger painting to do smudge painting, you can do it on a new layer without affecting the lower layers. I had the dry brush model layer turned off in this picture so you can see the finger painting progress. When you do a finger painting this way on a new layer, you can turn off the source to see where you still need to paint so you don't miss a spot.

The finger painting was done using different sizes of the fan brush. I changed the size of it quite a few times and used as small as 2 pixels for some of the finer details. For those who like to know how long something takes, it took me about 8 hours to finish the finger painting. I did not do it all in one sitting.

I played around with the colors a bit and decided the picture had too much light on the shoulder and not enough on the face so I rendered some lighting effects which you will see on the next step.

I used the spotlight on the render lighting effects. This placed the focus more on her face than her shoulder. I also added a canvas texture. Then I deleted the dry brush layer from step 3 because it was no longer needed.

I did some final dodge and burn adjustments and fixed a few things that needed tweeking.
This is a before and after shot side by side so it's easier for you to see the difference.