These are notoriously difficult to get feeding. I've had no experience with them, but finicky eaters often are enticed by live foods. Live brine was a good choice, I'd try live blackworms. They eat coral polyps and feast on coral in the wild, so this can be problematic in home aquaria because A) we like our coral and B) we don't really want to supply it for this purpose.
Those that have been trained to eat frozen seem to have been lured in to doing so by mixing several frozen foods and adding garlic guard, for example. I always mix 10 or so frozen foods, microwave, strain, and add selcon, zoecon, vita chem, and garlic guard. I omit garlic guard once everyone is feeding as long-term effects of using garlic may be pretty negative, but I don't know that that has been completely substantiated- it's certainly true however that garlic wouldn't ordinarily be a part of their diet in the wild so I omit it when it is no longer needed for new additions.
The best plan of attack is to buy one that eats before you purchase it. Although this is no guarantee that it'll eat in a new environment, it certainly increases your odds.