I think you have already pretty much answered your own question, The E71 being a series 60 phone should play with opensync which in itself plays with Evolution.
Nothing is out of the box (not even reliable sync with a Windows client) But a quick glance over some instructions Google gave me shows that it is a matter of installing a handful of packages and setting up the bluetooth pairing. On a sane disto it looks like it should take less time than it took me to write this reply.
http://www.wahlau.org/series_60_3rd_edition_nokia_n73_synchronization_with_o...
I run a series 60 phone as well. However I have never tried this as mine syncs over GPRS to Exchange 2003 (yeh boo hiss..but it works) which gives me live mail,tasks,contacts and calendar. Oh and a remote wipe the phone and lock it button for when it gets lost.
However it would still be interesting to hear how this works out.