Yes, it can. GSM and later phone protocols automatically adjust the phone's transmit power according to the strength of the signal it gets from the cell tower. It's just like how, if you're talking to someone and you can't hear them very well (because they're a long way away, or in a noisy environment), you'll tend to talk louder or shout, but if you can hear them clearly (they're right next to you), you'll talk more quietly. The phone works the same way.
Of course, for the phone, "talking more loudly" means putting more power into its transmitter, so the battery will be drained faster. If you switch to a network that has cell towers further away from where you spend most of your time, your phone will be using more transmit power more often, so it will use energy more quickly. Note that it's the received strength that matters (i.e. how much attenuation there is), not the quality of the signal, so you may find this happens even if you get a better signal overall.
Cell handover, when you move from one cell to the next one, also takes more power, and your new network's better internet speed might be a result of having denser cells in your area, leading to more handovers.
Finally, the worst thing for a phone is being completely out of range, because it has to periodically transmit on the maximum power to try to get a response from a cell tower. (This is why it's especially important to turn your phone off for a flight: once the plane gets out of cell range, all the phones will start blaring out as loudly as they can.) It's possible that your new network's coverage is much better at your home and your office, but during your commute, you haven't noticed that you leave the service area completely, and so your phone starts draining the battery then.
In summary, there are lots of factors, so it's hard to predict the effect of changing network operator, but it can have an effect. Of course, that doesn't stop it being a coincidence in your case.