In Vulgate, Matthaeus 4:23, it says "et prædicans Evangelium regni". Shouldn't it be "regno" (dative) rather than "regni" (genitive)? He was talking the gospel TO the kingdom, not the gospel OF the kingdom.
The Latin is a pretty literal translation of the Greek:
καὶ κηρύσσων τὸ εὐαγγέλιον τῆς βασιλείας
"τῆς βασιλείας" (tēs basileias) is genitive, not dative. He is preaching the Gospel of the kingdom, not preaching the Gospel to the kingdom.
This makes sense. The "kingdom" in question--as is clear from many other passages throughout the New Testament--is the "kingdom of Heaven" (ἡ βασιλεία τῶν οὐρανῶν) or (as Mark and Luke prefer to say) the "kingdom of God" (ἡ βασιλεία τοῦ Θεοῦ). It is the message, not the recipient.
A review of several English translations makes it pretty clear that this hasn't been a matter of dispute.
I am going to diverge from brianpck's answer. In my opinion the OP is correct, or at least partially correct. The translation in the vulgate is WRONG. Basically Jerome got it wrong when he translated it 1600 years ago.
Even though βασιλείας is indeed genitive, it is a genitive of place, not a genitive of possession. The Greek genitive is much different than the Latin genitive and can function as both an ablative and also in adverbial senses. In Matthaeus 4:23, the genitive is being used to indicate WHERE the action is taking place. So, in English it would be "... preaching the Good News in the kingdom ...". In Latin, it should have translated like this:
et prædicans Evangelium in regno
Where regno is ablative. Note that we see the same usage of the genitive in other parts of the Gospels. For example, in Luke 16:24 we have this
ἵνα βάψῃ τὸ ἄκρον τοῦ δακτύλου αὐτοῦ ὕδατος
which means "that he might dip the tip of his finger in water" where the word for water, hydratos, is in the genitive case, indicating WHERE he is dipping his finger. Note that Jerome got it right when he translated this latter passage, because he translated it as "in aqua" using a preposition with the ablative. In the passage in Matthew, note that the preposition should probably not be omitted. Sometimes, in Latin the word "in" can be omitted, but this is usually only when the place is proper noun, like Roma (in Rome) or something so big, that there is only one of them, like mare (in the sea).
More examples of the Greek genitive used to describe a place where the action is occurring:
ἦσαν ὁμοῦ Σίμων Πέτρος καὶ Θωμᾶς ὁ λεγόμενος Δίδυμος καὶ Ναθαναὴλ ὁ ἀπὸ Κανᾶ τῆς Γαλιλαίας (John 21:2)