Related Before the Establishment of Surnames - The common ancestor you share with individuals of different surnames on the Y-DNA line may be many, many generations back in your family tree, prior to the establishment of hereditary surnames (which occurred in England around 1300). This is the most likely reason for Y-DNA matches with individuals of different surnames.
Convergence - Sometimes mutations can occur through many generations in completely unrelated families which result in matching haplotypes in the present time frame. Basically, with enough time and enough possible combinations of mutations, it is possible to end up with matching or closely matching Y-DNA marker resuls in individuals who do NOT share a common ancestor on the male line. Convergence is more plausible of an explanation in individuals belonging to common haplogroups.
A Branch of the Family Adopted a Different Surname - this is another common explanation for unexpected matches with different surnames. The change in surname often takes place around the time of an immigration event, but may have occurred at any point in your family tree.
The likelihood of each of these possible explanations depends, in part, on how common or rare your paternal haplogroup is. Individuals in the very common R1b1b2 haplogroup, for example, will likely find they match many people with different surnames. These matches are likely the result of convergence, or of a common ancestor who lived prior to the adoption of surnames. If you have a more rare haplogroup such as G2, a match with a different surname (especially if there are several matches with that same surname) is much more likely to indicate a possible unknown adoption, a first husband you may not have discovered, or an extramarital event.