Difficulty in capturing enough electron correlation: The difference between the lowest states belonging to different electronic configurations can be small (for example, on the order of 1 kcal/mol). Traditional methods for full configuration interaction (FCI) calculations such as the Davidson method are unable to be used in any remotely accurate basis set for a molecule beyond a handful of electrons, but d-block elements have far more than a handful of electrons.
Take scandium for example, which is the first d-block element. Even if you freeze the neon core, there's 11 electrons. You are asking about molecules, so we must at least have a hydrogen attached to the scandium, so now we have 12 electrons to correlate. Even if we use the cc-pVDZ basis set (which is often not enough to get 1 kcal/mol accuracy in the difference between two electronic ground state energies), we would have 48 spatial orbitals. How many ways can you put 6 spin-up electrons and 6 spin-down electrons into 48 spatial orbitals without imposing any spatial symmetry restrictions? The answer is:
$$
{48\choose6}^2 \approx 1.5 \times 10^{14}. \tag{1}
$$
If each FCI coefficient were to be represented using double-precision arithmetic (8 bytes), you would need more than 1 petabyte to store all coefficients, and even taking advantage of sparsity won't help you get to size where traditional FCI methods will be convenient. More recently developed methods such as FCIQMC, SHCI and DMRG would be able to treat systems with $10^{14}$ FCI coefficients fairly well, but these methods are less black-box and have a bit more of a learning curve in order to understand how to determine that the calculations are properly converged. Furthermore, if you switch scandium with an element that has only 3 more electrons (chromium), and you switch hydrogen with an element that has only 2 more electrons (lithium, whose cc-pVDZ basis set is bigger than it is for hydrogen) the calculation in Eq. 1 becomes:
$$
{63\choose9}{63\choose8} \approx 2 \times 10^{18}. \tag{2}
$$
The calculation just became more then 10000 times bigger simply by switching scandium to an element 3 electrons larger and hydrogen to an element 2 electrons larger!
Finally, molecules containing d-block elements tend to have several FCI determinants which are nearly equal in importance, meaning that either FCI or multi-reference methods are required, as opposed to the highly efficient single-reference methods like those based on a coupled cluster model (this is what Roma's answer says).
Extra difficulties when involving f-block elements
Relativistic effects: The heavier the elements involved, the more that relativistic effects become important, which means that you need to know a bit more in order to know how to do the calculations properly. Furthermore, spin-orbit coupling starts to become more and more important, and this will make calculations more expensive, and will reduce the number of computer programs available for you to do the calculations (since not all electronic structure software packages have all methods implemented for the highly relativistic cases).
Even more electrons: If you thought that the examples in Eqs. 1 and 2 were hard, then just imagine $\ce{LaH}$ which involves the first f-block element and the lightest element in the periodic table. The cc-pVDZ-X2C basis set has 84 spatial orbitals and even with the krypton core frozen, you would have 21 electrons from the lanthaninum and 1 from the hydrogen, which means Eq 1 becomes 100000000 (10 million) times larger:
$$
{89\choose11}{89\choose10} \approx 2 \times 10^{26}. \tag{3}
$$
Lack of basis set choices available: Basis set choices are far more limited for the f-block elements compared to the smaller elements in the periodic table. This has improved a bit in recent years, but there is still some more progress to be made in this direction. You may need to optimize your own basis sets, or to resort to using pseudopotentials (which can be considered under the list of extra things you'd have to learn in order to do relativistic calculations).
Lack of programs that can treat basis sets with k-type orbitals: Most electronic structure software does not allow you to do post-HF calculations with k-type orbitals in the basis set, so you wouldn't be able to use a 5Z basis set on uranium, for example, in molpro, orca, gamess, the public release of cfour, or the publicly purchasable version of gaussian.
