But ideally the utility class should not be a part of the ear.
"Ideally?" I'm not sure where you heard that, but an enterprise archive is meant to contain all of the components that make up the application that's why you can define different module types (i.e. ejb, java, web) in your application.xml file.
But as soon as i remove utils.jar from the ear,i start getting classloading problems related to it.How do i keep the utils outside of the ear?
Once again, you shouldn't be worrying about this, but it depends on your application server. There is a probably a lib directory somewhere that contains server-wide class libraries that you can access from any application code.
But really, if your utils.jar contains classes needed by your EJBs, then it belongs inside the ear.