When the engine was replaced, did they replace all the filters etc?
Normally when they replace an engine they will just be supplied with the lump, not all that goes with it.
Got to be worth giving it a full service first before you chuck a load of money at it??