I was quite happy with the Sheraton Utama, especially the food was great! (Try the Sheraton burger, or what it was called.. the best I ever ate... yepp, in Brunei.. sounds strange :-) )
Rooms should be renovated now, I assume... when I stayed there, they were already renovating the top floor.
I've posted some photos
here.