I went from a 4.1 to a 6.1 conversion, the main hurtle here is the Windows to Linux. There are a few things to ask, first off, do you use and Emergency responder? If so make sure you upgrade that first. The only big issue I found with the upgrade was that even when I upgraded the emergency responder prior to the upgrade there was more configuration that had to occur on the CER server after the upgrade. I ended up calling TAC and the guy raced through it like crazy so I did not get all that he did but he changed some snmp settings, and the version of CM the CER server had stored. Then it was mostly verifying CTI Route point and users.
As far as just doing the upgrade it worked fine, no real issues there, hopefully you have a subscriber that will pick up the slack while you upgrade the publisher. Other then that expect to do some cleanup, I had to clean up some IPMA configs and such but nothing real major.
One last thing, make sure you make multiple copies of the data export, just in case, I had a copy on a flash drive, on my computer and on a server.
Oh, on last thing, you will have to setup backup again, there is no BARS that does the backup for everything, you setup each server to backup individually( I personally like this better) and it is real easy to do.
We have just been through a 4.2(3) to 6.1(2) migration, and there were a number of issues which arose. The migration I'm now working on is 4.1(3) to 6.1(2), and while it was useful knowing what issues had arisen with the first migration, we are experiencing a different set with this upgrade. Separately, lab testing of a 4.1(3) to 6.1(3) migration produced no issues - so you will have to be careful with others' experiences if they are not exactly the same as the upgrade path you are planning. If the upgrade path is the same, you should also check whether the others make use of extension mobility, as differences there can affect what issues may arise.
If you are intending to re-use the 4.0(2) servers, strongly recommend you source additional hardware so the Publisher migration can be tested without impacting the operational system.