Themes can change three things:1) the layout of the While-Playing Screen ("WPS", the one that shows track and timing information while a track is playing) and RWPS (same thing on the remote), 2) the font used in all screens and menus, and 3) (but none of the included themes do that as far as I know) the background image for the menus
When you say "nothing seems to change", do you mean immediately (while you're still in the menu) or have you checked the WPS?
Have you downloaded the fonts package? The fonts are a largeish block of data that don't change very often, therefore only the rockbox default font is included in the daily builds. If you (or the theme you choose) want to use any other fonts, you'll have to add them to your rockbox first.