First, there is nothing wrong with our charge polarity conventions. They are predict electrical phenomena just as accurately as the opposite convention would have done.
Did we have a problem if since the begin of their discovery we called them positive particles and negative to protons?
We could predict the behavior of electrical phenomena equally well with either convention. With a positive-electron convention, we'd still have to deal with negative carriers when we study ionic transfer (batteries, for example) or hole transfer (in semiconductors).
But there was no question of defining electrons as negative from their discovery, because the convention of negative and positive charge was already established before the electron and proton were discovered.
why do we say that electrons have negative charge? Is it a question of convention or is there some deeper knowledge that implies them to be negative?
It is entirely a matter of convention. This convention was established before the electron was discovered. It was known since the ancient Greeks that rubbing certain substances (fur, amber, etc) could produce a state where they attract or repel each other. According to Wikipedia, it was C. F. DuFay who proposed, in 1733, that electricity has two types; and Faraday who proposed, in 1839, that these two types are opposite polarities of a single phenomenom.
As for when we discovered that electrons are negatively charged, according to Wikipedia,
The German physicist Johann Wilhelm Hittorf studied electrical conductivity in rarefied gases: in 1869, he discovered a glow emitted from the cathode that increased in size with decrease in gas pressure. In 1876, the German physicist Eugen Goldstein showed that the rays from this glow cast a shadow, and he dubbed the rays cathode rays. During the 1870s, the English chemist and physicist Sir William Crookes developed the first cathode ray tube to have a high vacuum inside. He then showed that the luminescence rays appearing within the tube carried energy and moved from the cathode to the anode. Furthermore, by applying a magnetic field, he was able to deflect the rays, thereby demonstrating that the beam behaved as though it were negatively charged.
So the negative charge of the electron was determined by Crookes in the 1870's, about 30 years after Faraday established the principle of negative and positive charges.
And even after the electron charge was known to be negative it wasn't until 1911 that Rutherford published his nuclear model of the atom, establishing the electrons role in atomic structure. I can't find a date, but presumably it wasn't until after this that we knew the electron was the charge carrier for currents in metals.