Brine shrimp are good to supplement with other food but in themselves are not very nutritious.
I would get a plastic turkey baster and a shot glass. Put some water from the tank in the glass and thaw some mulchy frozen food that has a ton of stuff in it like Formula1. I am sure there is other stuff too, but pick up some Forumla1 as well.
Then suck the stuff up with the turkey baster and slowly get it near the goby after feeding your other fish (so they don't eat all the goby food) and release some. He should go for it. Formula used to fatten up my fish and make them quite colorful. heh. If they only knew how much I recommend them.. hmm..
Anyway that should help. It helped with my Diamond Goby. He loved it.
matt