You have to think about what exactly a cathode and anode are. You are falling victim to this:
A widespread misconception is that anode polarity is always positive (+). This is often incorrectly inferred from the correct fact that in all electrochemical devices, negatively charged anions move towards the anode and positively charged cations move away from it. In fact anode polarity depends on the device type, and sometimes even in which mode it operates, as per the above electric current direction-based universal definition. Consequently, as can be seen from the following examples, the anode is positive in a device that consumes power, and the anode is negative in a device that provides power. - Wikipedia
It's your conditioning from other chemical nomenclature--"cation" and "anion"--which are absolute about their charges.
So beyond misleading nomenclature, what does cause this to happen?
Take this picture for example: http://img.sparknotes.com/figures/0/02480ae8fc1a41b131a3fdb5a698e9a3/compare.gif
If E°cell > 0, then the process is spontaneous (galvanic cell)
If E°cell < 0, then the process is nonspontaneous (electrolytic cell)
where E°cell = E°(V) reduction + E°(V) oxidation
In your case,
Pb → Pb2+ + 2e- = 0.13
2Br- → Br2 + 2e- = -1.06
E°cell = .13 - 1.06
E°cell = -.93
In your case, the process is nonspontaneous (makes sense, think about trying to reduce ionized bromine), so you're looking at an electrolytic cell, which is battery driven (it needs work put in to operate.)
So, again, to directly answer your question:
In the electrolysis reaction, lead is formed at the cathode and bromine is liberated at the anode. But why is it so? I mean, before gaining or losing electrons to become neutral, lead is positive and bromide is negative. So, naturally they should be attracted to the cathode and the anode respectively.
Lead is formed at the anode because work from a battery was put in that pushed the reaction in that direction. Before work was put in, the reaction would have proceeded in the opposite direction (think exothermic vs endothermic, but in this case spontaneous cell potential vs nonspontaneous cell potential.)
But why do they become neutral after they reach the electrodes.
They become neutral at the electrodes because that is where the reaction happens, and that is where the electrons are transferred.
Why do they gain electrons at only the electrodes to become neutral?
Again, where else could they gain electrons? They are sitting in a solution contain themselves and their respective anions, which they have already reacted with, and will no longer be transferring electrons with.
