Try the following -

Right click the Spotify executable and select 'Properties'. Then select the 'Permissions' tab and put a tick in the 'Execute' tick box.

Install via Wine as usual.