OK, what kind of guitar is it and what kind of trem? Some trems are crap, and won't work fantastically well no matter how well setup.
Even the most decrepid, grungiest, POS lo trs 2 will eventually get in tune at some point. what happens after you touch the bar is another thing all together.
OP, for starters, it sounds like your springs are WAAAYYYY too loose. You need to tighten them down a lot it sounds like.
Trick of mine, and I've seen others do it to, take a bottle cap off a 20oz coke or something like that, and wedge it underneath the bridge. The bridge will now sit on top of the bottle cap and it should hold it tight.
Now, start putting strings on and tightening them down. Every so often check the tension on the bottle cap. If you can start wiggling it around freely, tighten the springs on the back until you cant move it anymore (not too tight!). This process will take a while, and you need to repeat as needed to keep it in tune. Once your strings are all on and in tune, make sure the cap is still tight, but just barely. ease out the cap and release the trem. It should be CLOSE to where you need it to be.
Also, keep in mind, new strings + floyd rose = headache for a while. its GOING to go out of tune. In fact I dont even bother tightening the lock nuts until I beat on the new strings for 15-20 minutes (bends, whammies, hard strumming). Tune, repeat. Tune, repeat. I can set a guitar to float in 5 minutes now, but it still takes a while for the string tension to settle on the guitars and the strings to stretch enough to get a stable tune.