I am assuming you are talking about smart playlists. I don't believe live updating on an iPod will happen for smart playlists which rely on other smart playlists that are NOT on the iPod. I have one smart playlist which contains all my podcasts, based on genre and some other criteria, and feeds all other podcast smart playlists. If I don't include that smart playlist (and all the other ones used to build the final playlists)...I don't believe my other playlists will update until I re-sync with iTunes.
I went to iLounge to find something in the forums to confirm my post and I found this. It confirms my thought and also indicates that the new OS 3.0 breaks live updating for any smart playlist which relies on another smart playlist.