The nucleation of solid Al from the melt by TiB2 is well established and is believed to involve the formation of Al3Ti. Since the atomic-scale mechanisms involved are not fully understood, we look to computer simulation to provide insight. As there is an absence of suitable potentials for all of this complex system we have performed large-scale density-functional-theory molecular dynamics simulations of the nucleation of solid Al from the melt on TiB2 and Al3Ti substrates at undercoolings of around 2 K. Using periodic boundary conditions, we find limited ordering and no signs of incipient growth in the liquid Al close to the B-terminated surface of TiB2. By contrast, we see fcc-like ordering near the Ti-terminated surface, with growth being frustrated by the lattice mismatch between bulk Al and the TiB2 substrate. The Al interatomic distances at the Ti-terminated surface are similar to distances found in Al3Ti; we suggest that the layer encasing TiB2 observed experimentally may be strained Al on a Ti-terminated surface rather than Al3Ti. For the Al3Ti substrate, fcc-like structures are observed on both sides which extend rapidly into the melt. Periodic boundaries introduce unphysical stresses which we removed by introducing a vacuum region to separate the liquid from the solid at one of the interfaces. We see ordering in the Al on both the B-terminated (0001) surface of TiB2, and on Al3Ti(112), with the ordering able to be stronger on the Al3Ti substrate. However, we cannot draw strong conclusions as these simulations need more time to allow long-ranged fluctuations in the liquid Al to dampen out. The huge computational cost restricted the range and duration of simulations that was possible.