Time Machine Server - one MBP can back up, another can't. Why?
So, the problem was that the second MBP needed the Time Machine server credentials User in all lower case. The Mac mini has a local user, let's say Arthur. I configured the second MBP to use the credentials Arthur/(a password) and the connection wouldn't work. Configuring it as arthur/(a password) worked just fine.

Thanks to Allan I found this by mounting two volumes from the Mac mini, one using SMB and one using AFP, and noticed that the AFP mount showed the user as 'arthur', and the SMB showed the user as 'Arthur', even though I'd logged in as Arthur for both mounts.