I don't know if it helps, but I'm using Trinity 3.5.12 on Debian Squeeze with the NVIDIA proprietary drivers. I don't have multiple monitors, but randr seems to work fine. I can resize from the tray icon anyway.
Using nVidia here as well. In fact, my primary development machines use nVidia cards. :-)
While nVidia does not have XRandr 1.3+ support (and therefore cannot handle multiple monitors, etc.) this does not break Trinity. The appropriate configuration options only become available if the underlying hardware supports them.
If you really want multiple monitors via XRandr with nVidia cards, try the nouveau drivers. Be aware that they do not support 3D well at all at this time however.
Tim
Oh, and I forgot to mention that if your distribution does not support the newer versions of XRandr the appropriate course of action to take is to turn off libkrandr and krandrtray completely. I do not want to get into legacy support of older, possibly malfunctioning graphics subsystems unless I am paid to do it! ;-)
Tim