If you booked the flight together then it is very probable that it's seen in the booking system that you travel together. So it was probably a little bit mor that just his "word". (I'm, however, not judging if it was correct action on the counter stuffs behalf.)
A friend of mine was once travelling to Bali and she posted pictures of the boarding pass on Twitter. It was a few weeks after the CCC talk by Karsten Nohl and Nemanja Nikodijevic (https://media.ccc.de/v/33c3-7964-where_in_the_world_is_carme...), so I warned her that it might be not the best idea to post these images. She was very self-assured and replied that she's almost in the plane so there's not much risk.
I've asked if it would be OK for me to test and she was fine with it. I could log in to her booking without problems (booking code and the name which I knew anyway were on the images). In the system I saw the other person she was travelling with., I could change seats and names of passengers. I think I could even change the date of the flight back (but I'm no longer sure about it).
But this is how I'm pretty sure that if you've booked together, this might habe been visible in the booking system.