From the reading of the Rambam Hilchos Teffilin 3:14 it would seem that any color would be sufficient. The outer side of the retzuos are what is necessary to be black since that is a halacha L'Moshe M'sinai. The Rambam does note that it is beautiful for all of the teffilin to be completely black .
Text of Rambam :
וְלֹא יִהְיֶה אֲחוֹרֵי הָרְצוּעָה לְעוֹלָם אֶלָּא כְּעֵין הַקְּצִיצָה אִם יְרֻקָּה יְרֻקִּין וְאִם לְבָנָה לְבָנִים. וְנוֹי הוּא לַתְּפִלִּין שֶׁיִּהְיוּ כֻּלָּן שְׁחוֹרוֹת הַקְּצִיצָה וְהָרְצוּעָה כֻּלָּהּ:
Chabad Translation :
The back of the straps should be the same color as the compartment; if it is green, they should be green; if it is white, they should be white. It is attractive for tefillin to be entirely black, the compartments and the entire strap.
However, in the very next halacha the Rambam explains that if one covers his teffilin with gold they aren't acceptable. This is based off the Mishna in megillah. Some meforshim learn that the invaildiation is the material isn't from an animal. While other learn that it's a color issue and black must be used (pshat in the Yerushalmi ,not like the Rambam).
In conclusion, it would be rather odd that Mordechai would do something that is considered invalid by the Mishna.
Text of Rambam 15:
"If, however, leather from a non-kosher species was used or if they were covered with gold, they are not acceptable."