Obtaining caller ID, processing it and displaying it is actually a fairly complex process involving the caller's operator, yours, your SIM and your phone's software.
If all you see when someone calls you is "Call 1" or "Private number", no actual phone number, then you're not receiving caller ID at all. This can be because the caller is in fact concealing their number (you can do this on a GSM phone by prefixing the number to dial with #31#). In this case, there's nothing you can do.
If the caller IS sending out their caller ID but you're not receiving it, then the problem lies with your network and/or with your SIM. Give your operator a call. The chances are they can remedy this with an over-the-air update of your SIM card.
If you are now receiving caller ID but your phone isn't displaying the corresponding contact's name, it's because it can't tell whose number it is. There are many possible reasons for this, the three most common being duplicate numbers, international format and operator-branded firmware. There's also a quirk in SymbianOS that can potentially come into play.
If multiple contacts have the same number in your contacts list and one of them calls you, your phone has no way of knowing which one is actually on the other end of the line and, quite sensibly, just shows the number instead of trying to "guess" who it really is. Now, most phones can store contacts both in their own memory and on the SIM card. If you have the same contact in both locations then that counts as duplicates and you'll never see that contact's name displayed. The cure for this is to use the phone's built-in search facility and to search for the number in question. If you find it more than once then you'll have to delete all but one occurrance.
Another potential cause is storing the numbers in the "wrong" format. Always store your numbers in international format. Not only does it provide a uniform platform for number detection to work from, it also makes calling your home-country contacts easier from abroad. Assuming you live in the UK as I do and your contact's mobile number is 07890123456, don't store it in your contacts as such, use the international format instead. Prefix the number with a "+" sign (obtained by pressing the "*" key twice in rapid succession on Nokia phones) and the international prefix ("44" in the case of the UK) and strip the leading zero. You end up with:
+ 44 7890123456 (don't include the spaces, they're printed here for clarity)
In many countries, the UK included, the international dialling prefix is "00", so some people think they can get away with using "00" instead of the "+" sign because they don't know how to enter the latter.
Well, they can't.
The phone won't recognise the number as being an international number because it doesn't start with a "+" and therefore won't be able to do a certain number of automatic transformations. Also, it won't work in all countries. In the USA, for example, the international prefix is "01", not "00", so if you take your phone over to the USA and try to ring someone at home, you won't get through and you might also incur roaming charges. It has to be a "+" sign.
Also bear in mind that synchronising with Outlook tends to mess up numbers. Microsoft very helpfully add spaces and a "(0)" in the number sometimes to make it easier for humans to read. It does however mean that the number is altered and therefore incorrect.
Finally, quite a few problems of this nature are down to operators messing things up when they alter the firmware in handsets that they distribute (read here for more information). In some cases it is possible to get written permission from the network operator to remove their buggy firmware and install generic Nokia firmware in its place in order to eliminate this problem (and others besides), but it's far from easy in an industry so tightly controlled by the networks. Characteristic tell-tale signs of operator ineptitude are the phone being able to display the contact's name when that contact calls you but not when they text you, or vice-versa, depending on whether you've stored the contact's number in international format or not.
There is also a bit of silly "optimisation" in SymbianOS itself, which can rear its ugly head from time to time. The operating system only compares the last 7 digits of the caller ID number it's receiving with entries in its contacts list. The probability of two people sharing the same 7 digits at the end of their phone number is one in ten million, but it has been known to happen. In this case, the phone can't distinguish between the two. So, for example, +441204123456 and +33634123456 are percieved as being the same number when they're clearly even in different countries (the UK and France). If one of those calls you or sends you a text message then the name will not be displayed because the phone doesn't know which one it is.
Caller ID in text messages is also a bit of a problem sometimes.
Assuming the phone is clear of operator-induced problems (see above), if it can't identify the contact correctly when they're calling you, it won't be able to identify them any better when they text you. So, you fix the problem, and yet the text message you received earlier still shows a number as the sender and not the contact that the phone is now able to identify correctly. Why is that?
It's because the list of messages displayed is built as and when inbound messages arrive. It is not updated every time you look at the list (think of the overhead that would be for phones with thousands of messages in the list!). The phone was not able to identify the contact at the time the message was received, so that's how it stays.
So, in short:
1) Eliminate duplicate entries, including on the SIM card.
2) Make sure all your numbers are in international format with "+" as the international dialling prefix.
3) If problems persist then it's related to operator branding.
4) SymbianOS only looks at the last 7 digits of phone numbers.
5) SMS/MMS message lists are built as and when messages are added, not in real time.