I like using my mobile phone as a PIM, but I don't like the built-in calendar that comes with Nokia phones. It's simply too basic. For example, you can't change one of a recurring set of appointments without changing all of them.
While I don't think the calendar software available for Series 60 (S60) phones is as good yet as the DateBk 3/4/5/6 application for Palm PDAs, the best I've found so far for S60 is AquaCalendar. I used it on my Nokia 6680, and I also have it on my Nokia E61. The good news is that the latest version of AquaCalendar for S60v3 (which covers new Nokia phones like the E61), AquaCalendar 5.05, is now working well enough to recommend to you. The calendar API apparently changed for the new S60v3 phones, and it took a while for them to port the software and fix the bugs. However, 5.05 is looking pretty good.
If you are fed up with the calendar in your Nokia phone (or other Symbian phone/PDA), you could do much worse than give AquaCalendar a try.