I sure hope you are in Europe. The 5110 is an old nokia that only operates on GSM 900. If you are planning on using this phone in North America you are out of luck. Assuming you are in Europe, European GSM providers use 900 and 1800 bands. Tmobile Europe uses 1800 only in some countries. 900 only in others. In some countries it uses both. What countrie(s) will you be using the phone in? Here is a list of countries/companies/and frequencies used in Europe. http://travel-island.com/gsm.phone/3gsmphones.html. If it is 1800 only then it wont work. If it is both 900 and 1800 then you will have limited coverage. If it is 900 only then you will be fine.
If you got a message that the "phone is not SIM restricted", I bet that the phone is already unlocked. And the person you got it from may not have known the difference. The true test is to put in a friends SIM from someone other then "Orange" and see if it works. Also make sure they have GSM 900 coverage. If it works then the phone is unlocked. Then make sure the phone is compatable with where you need it.