Is it possible to use colored coins with stealth addresses?
My main consideration being that coloring a unit of cryptocurrency requires being able to keep track of its exact location at all times with a public blockchain
Yes, this should be possible.
A "stealth" transaction still sends the colored coin to a specific ordinary address, and anyone can see on the block chain that this address owns that coin.
The only difference with stealth transactions is that this ordinary address, rather than being generated from a private key by the recipient in the usual way, is generated by the sender using the recipient's stealth address. This is done in such a way that the recipient, using additional data included in the transaction, can compute the private key. They can then redeem the transaction like any other ordinary transaction.
In this writeup in the example in Sections 9.1-9.2, the "ordinary address" in question is 1BjqrpQqr4tY5YPQkL8aG7NGkFbTbiuVu.
See also my answer here.