Are there any patches that are necessary, or may it be, that the network is not willing to provide a non-encrypted connection?
The network will indeed most likely refuse you as you found out.
Nothing you can do about it, the network is the master and since the specification says a phone _must_ support A5/1, the network is totally in its right.
Cheers,
Sylvain