Like, the neighboring grave? No, does not matter.
Dog too big?
For that matter, man too big?
Someone else have dibs on the dead dog?
NO
NO
NO
Was his body radioactive?
NO.
Suicide?
NO.
Did they find out after the man had died that the dog had let a will stating
that it wished to be buried somewhere else ?
Could they have buried the man and dog together?
NO. 
Not for sure.
Did the man enter into the agreement knowing he wouldn’t really end up being buried in that cemetery (just wanted to get the dog in)?
Did something happen at the cemetery between the man’s death and the dog’s that made the agreement impossible to honor?
Did the cemetery go out of business?
Was some kind of law or other legal mumbo-jumbo invoked to prevent the man’s burial there?
Word count.
Did something happen to the cemetery that prevented the man from being buried there?
Did some other entity claim the man’s body?
NO
NO
Were both man and dog bodies available?
I got this.
It was a military cemetery and the man was a veteran and the dog was a military dog. After the man died and was buried the dog was dishonorably discharged and so couldn’t be buried in the military cemetery.
I don’t think @Saint_Cad 's guess is completely correct, but I think it might be partly…
Was it a military cemetery?
If the circumstances were exactly the same except without the dog, would the man have been buried in the cemetery?