Sorted! To all having the same issue (without any help so far...) - an update of Java was needed.
Odd. I'm not aware of Adobe programs needing Java at all to work right.
Well I was not as well. Thats why I was so surprised...
I restarted Mac and immediatelly after I got message kind of "Adobe bla bla bla needs Java update. Do you want to install it now?" I confirmed, download started and when it was installed Adobe Premiere CS5 started to work.
Funny is (and I would blame Apple for that) that I was not able to install Java before - I had to wait this stupid dialogue.