I'm almost sure that if you ask a Persian speaker, he/she would tell you that the first sentence sounds a little bit odd, but not wrong. And actually, it's not wrong. Because با can mean either 'with' or 'and'. In case that it means 'and', it changes its role from preposition (which is usually 'with') to a conjunction (which is 'and'). Therefore it depends on how you're dealing with the subject here (او=u). Consider this example:
He went there with Ali
1. Ali accompanied him: او با عَلی رَفت
2. He AND Ali went there: او با علی رَفتَند or او و عَلی رَفتَند
(Source to check the role change for با: Moein Persian Lexicon)