> I've worked in other European countries without any problems (I'm from one of the ex-Soviet states)

Immigration in Switzerland is much different than in EU-member states.