Rashi offers two explanations:
of the family of Judah: And he was a Levite from his mother’s side. However, our Sages said (B.B. 109b) that since he committed deeds like those of Menasseh (i.e., he committed idolatry) who came from Judah he is called “Of the family of Judah,” but he was really a Levite the son of Gershom the son of our teacher Moses, as is stated below, (18:30) “And Jonathan the son of Gershom…”
The first explanation is that the man's tribal status, as usual, comes from his father, from the house of Judah, and "Levite" refers to his mother's family. The man wouldn't be counted as a Levite for any real purposes (temple duties, land allocation, etc), but it's something in his background that the text points out.
Alternatively, he's not actually of the family of Judah but is being associated with them because of their practices, as has been done in other cases in the text (according to the talmud). This is explained in the Babylonian talmud, Bava Batra 109b, arising from a discussion of tribal association and inheritance law. The following translation and notes are from the Soncino edition:1
[But] is not the mother's family regarded [as the proper] family? Surely it is written, And there was a young man out of Bethlehem in Judah — of the family of Judah — who was a Levite, and he sojourned there; [now], this is self-contradictory, [for] it is said, ‘who was a Levite’, which clearly indicates that he descended from Levi, [and it is also said], ‘of the family of Judah,’ which clearly shows that he descended from Judah; must it not then be concluded that his father [was of the tribe] of Levi and his mother [of that] of Judah, and [yet the text] speaks [of him as] ‘of the family of Judah’!
Raba, son of R. Hanan, replied: No;22 [he may have been] a man whose name was Levi.23 If so, [is] this [the reason] why Micah said , ‘Now know I that the Lord will do me good, seeing I have a Levite as my priest’?24 — Yes; [he was glad] that he happened to obtain a man whose name was Levi. But was Levi his name? Surely his name was Jonathan, for it is said, And Jonathan the son of Gershom, the son of Manasseh, he and his sons were priests to the tribe of the Danites?25 — He said unto him: But [even] according to your argument, [it may be objected], ‘Was he the son of Manasseh? Surely he was the son of Moses, for it is written, the son of Moses: Gershom, and Eliezer’; but [you must say that] because he acted [wickedly] as Manasseh,27 the Scriptural text ascribed his descent to Manasseh, [so] also here29 [it may be said that], because he acted [wickedly] as Manasseh who descended from Judah, the Scriptural text ascribed his descent to Judah.30 R. Johanan said in the name of R. Simeon b. Yohai: From here [one may infer] that corruption is ascribed to the corrupt.31 R. Jose b. Hanina said: [This may be inferred] from the following: [It is written,] And he (Adonijah) was also a very goodly man, and he was born after Absalom; was not Adonijah the son of Haggith, and Absalom the son of Maacah? But because he acted in the same manner as Absalom who rebelled against the king, the Scriptural text associated him with Absalom.
(22) His father was not of the tribe of Levi, but of that of Judah.
(23) לוי may be rendered as both ‘Levite’ and ‘Levi’.
(24) If the young man were not of the tribe of Levi, would Micah have been so glad in having secured a mere layman as his priest?
(25) Judg. XVIII, 30. The Danites appropriated Micah's graven and molten images, his ephod and teraphim, and took also with them the young man who was his priest.
27) Manasseh the son of Hezekiah was one of the most wicked kings of Judah. Cf. II kings XXI, 1-17. [In the M.T the נ of מנשה is a litera suspensa.]
(29) To harmonise Judg. XVII, 7, with the statement that the family of the mother is not regarded as the proper family.
(30) But, in reality, he may have belonged to the tribe of Levi. Hence, in either ease, Judg. XVII, 7, cannot be adduced as proof that the mother's family is regarded as the proper family.
(31) Micah's priest who ministered to idolatry is described as a descendant of the corrupt king Manasseh.
1 I've included only the notes that bear on the present question.