Recent iTunes purchases can only be found on my iPod using search (i.e. they are not browsable by Artist/Title/Album....

Older purchases can be accessed in the traditional fashion. But all the purchases I've made in the last couple of months can only be found using a search (e.g. for artist or song/album title). I am using a 4th Generation 64GB Touch that is otherwise in perfect working order, with latest iOS (at least, iTunes tells me it is when I 'check for update').