Is this in the U.S.? Did you do it by yourself or did you hire an attorney?
When you file a trademark application in the U.S., it is very common to get an initial rejection but that is not the end of the story. You have the opportunity to argue to the trademark office that the rejection was incorrect, and these arguments are often successful and you end up getting your trademark.
Perhaps your trademark application was too broad (in that you gave too broad a description of the goods and services associated with the trademark) and you might succeed if you narrowed your application.
EDIT:
Does the other company have a registered trademark? If not, then the fact that your are in separate geographic locations could protect you. For unregistered marks, you only have trademark rights in the areas where you use your trademark. You wouldn't need to make a deal.
If the other company has a registered mark, then that gives them nationwide rights. I don't recommend trying to make a deal as they will almost certainly say no. You could just start using your trademark and see what happens. The most likely worst situation is that they send you a C&D letter and you change your company name.
Why not reapply for your trademark with a narrower application?
Why are you asking these questions here instead of asking your trademark attorney?
