Assuming you're using the web part, I'd suggest setting the web part's caching to 0. It's most likely caching the data upon retrieval.
Another option is to simply use a repeater and select the TOP 1 and set the order by property to
newid(). This works every time no matter what your caching settings are.