I'm somewhat similar to your argumentative colleague. I have strong opinions and I love to argue because I believe that through a good argument, both sides can come out with more wisdom than they went into the argument with.
Some people are hard for me to work with because they don't respond when I start a discussion, or they just drop a statement without any arguments to back it up. To me, this feels like they're saying "This is the objective truth but I won't bother to explain why" which clashes directly with my need to know why I am wrong if that happens to be the case. This seems applicable to your situation: perhaps if you had provided a deeper explanation of your ideas from the beginning, you could have convinced your colleague and saved the both of you the time it took to work on the 'wrong' solution?
One of the most productive coworker relationships I ever had was with a coworker whom I had a very difficult start with, until he realised that I am not just arguing for arguments sake but am inviting him to explain his ideas to me so that I can understand it and we can consider the pro's and con's of the idea together by discussing it.
On the other hand, some people are worse than me and will say 'no' to any idea that isn't theirs, just because it didn't come from them. Those people are a lot harder to deal with because they're not actually interested in what you have to say. In this case, you probably want to talk to your manager and explain that you're having difficulties working with this colleague because you feel that they don't value your knowledge and experience.
In the end, you'll have to try to figure out which of these two cases applies. I would advocate trying the approach of explaining your ideas further first, since this gives you a strong argument if it turns out to be the second case: you'll be able to say to your manager something like "no matter how well I explain my ideas and back them up with arguments, [coworker] just doesn't seem to listen to me and just shots me down at every turn".