Actually, from what I've read, Andreas Katsulas didn't like playing the character in person because he then had to be aware of all his movements and ticks and such. He was apparently happier when the character was just a face on a viewscreen. I personally would've just kept the character of T'Rul around. I liked the idea of a Romulan on the bridge, just as we had a Klingon on the bridge seven years prior. I could understand if they felt a character wasn't working, but it seems like they didn't even try.
I thought this was DS9's biggest failed opportunity. I think a Romulan ambassador type character would have gave the show more depth when the Romulans become a focal point in the Dominion War.