A possible explanation for these results is that you have more than one relationship – maybe you are half-siblings and also share a more distant relationship on your mother's side. For example, the man may be your half-brother because you share a father, and also be a second or third cousin via his mother.
Just to diagram this possible scenario to give you an idea (there are many other possible permutations):
? ┬ ? ? ┬ ?
? ┬ Father ┬ Mother
This would explain the larger than average autosomal match for a half-sibling. However, you are unlikely to only share a father because you have an X-DNA match, meaning you are likely related through your match's mother (since he did not inherit any X-DNA from his father).
You really need more DNA evidence to be sure. A possible way to proceed with this is to do a mitochondrial DNA test with this man, as this will only show a match if you are related through a direct maternal line (even if much more distant compared to your close relationship as half-siblings).
You might also consider asking if your possible half-brother has any other family members he could consider testing. For example, if he has an aunt or cousin on his mother's side who could take an autosomal test, it would be interesting to see if there is any autosomal or X-DNA match there.
This scenario is particularly likely if both your parents have ancestors that came from the same area. It was not uncommon for distant cousins to marry each other – two of my grandparents were cousins. You could therefore also approach this problem from a more traditional genealogy approach. It would be worth comparing your family trees several generations back on both your and your match's maternal and paternal lines. Look for ancestors who came from a similar area, you might be lucky and find a paper trail for a more distant relationship with this match.
The bottom line is don't get fooled into thinking you have to be one of the simple relationships suggested on your results – it could be a much more complex combination of relationships.