In the Matthew passage, Peter and Andrew are together fishing. In the John passage, Andrew was with John the Baptist and Peter was else where?
Before reconciling the synoptic account, generally, with John's account, it is first necessary to reconcile the different versions of the synoptic account.
Wikipedia tells us, "
Issues to be reconciled
In both Mark and Matthew the meeting by the Sea of Galilee seems to be the first time Jesus has met the brothers, and we learn in Mark 3:16 that Jesus surnames Simon as Peter, with Mark indicating that Simon's name was changed on this occasion.
In John 1:35-42, Jesus most certainly first met Andrew with John the Baptist and first met Simon shortly afterwards, when Andrew called him. It was at this time (John 1:42) that Jesus called Simon by the name Cephas, or Peter.
In Matthew 3:13-14, John the Baptist immediately recognises Jesus, but John 1:31,33 has the Baptist twice saying that he had not known Jesus when he came to be baptised. However, Mark makes no mention of this, so the contradiction can be overlooked for present purposes.
The scope of the problem with any attempt to harmonise the synoptic gospels and John's Gospel is summarised by Burton L. Mack, who says in Who Wrote the New Testament, page 177 that the Jesus, setting and storyline of the fourth gospel can not be aligned with the synoptics. It has not been possible to meld John's Jesus with that of the synoptics as if each had merely emphasised different features of the same historical Jesus. He says John's Jesus is an altogether different kind of being.
Elaine Pagels says in Beyond Belief, pages 61-63, that she discerns in John’s Gospel a distinct bias against Peter. John Dominic Crossan, in The Birth of Christianity, page 566, also points to typically oblique examples of the exaltation of the Beloved Disciple over Peter in John's gospel. So, a theme of John's Gospel seems to be to undermine what its author might have felt had become excessive veneration of the apostle Peter.
In keeping with the resolve to minimise the role of Peter in the gospel story, he is no longer the first disciple selected by Jesus, only following Jesus at the insistence of his brother, Andrew. At the same time, Andrew becomes the first to declare Jesus to be the Messiah, or Christ, at the very beginning of the gospel (John 1:41). In Mark's Gospel, Peter is the first disciple to venture that Jesus is the Christ, and only at verse 8:29.
John does not include a list of the disciples, corresponding to 3:14-19, so simply moves the renaming of Simon forward to this first meeting, where the difference passes unnoticed.
I don't see an inherent conflict between these passages. Specifically, the John passage describes how both Andrew and Simon initially met Jesus; the Matthew passage describes how He called them as disciples. Matthew never claims that the event by the seashore was Jesus' first encounter with the brothers.
Edit: In the account of John, Peter meets Jesus just after Jesus had been baptized, been tempted in the wilderness, and came back (John 1:32-34). Peter's calling is in all of the gospels. In Luke, Jesus was tempted in chapter 4. Afterward, in chapter 5 (coinciding with the chronology in John 1), he calls Peter as a disciple (his calling is paralleled in Matt 4 and Mark 1). In Luke 4:38-39, just before Peter and Andrew were called, Jesus went from the synagogue to the house of - wait for it - Simon! He went to heal His mother in law! This is before Jesus called him as a disciple. Also, in 5:3, he first refers to Peter simply by the name of Simon, just like in 4:38, so we can safely assume it is the same Simon whose house He had visited (otherwise Luke should have/would have given him a distinction, like Simon the fisher, in order to clarify it wasn't the Simon discussed only about ten verses ago in chapter 4, right?) Jesus called him after healing his mother in law! Of course He could have met Him as discussed in John 1 with his actual calling taking place soon after! Does anybody see a flaw or hole in this line of logic?