You can do several things to overcome this problem. After you inserted the new SIM card and turned ON the device, go to its Menu > Settings > Wireless and network > Mobile networks > Network Mode and make sure that Auto mode is selected. By doing this, your phone will automatically search for all networks, GSM or WCDMA. If your phone can't find the network, contact the provider which sold you the SIM card for additional support.