One of the funny things that happened in moving to Vienna is the process we had to go through for me to obtain permission to work. Actually, it's only funny now because it's over.
I wanted to start my own business (Vienna Transport Strategies) and so I went to the Chamber of Commerce, they were able to register me in about 5 minutes, but to complete the registration I needed to have permission to work. However, the city department responsible for giving me permission to work could not give it to me because I had no job.
Get it: you cannot start a business because you do not have permission to work, but you cannot get permission to work because you do not have a business.
The happy ending came when my wife got a job, then I was able to get permission to work as the spouse of an Austrian!