To name a few: Subdivision Surface could help. Also, Multiresolution and Smooth (not sure if this Smooth is different from what you used).
But I would use the subdivision so that you would have more locations in which you can control the number vertices.
You haven't stated where the seams are located and how it was uv unwrapped, both can cause or change how the model looks, especially, if they were not unwrapped correctly... like a cylinder would be unwrapped strangely (causing stretching, etc.) if not done correctly. If it was not UV unwrapped correctly all maps associated with that area could appear incorrectly.
Smart UV mapping (box shape, the only thing that it's really good at) on complexed shapes it's not the best way to go. UV unwrapping can be the most complicated to understand and fulfill correctly. There are many YouTube videos (for both, 3dsMax & Blender) on UV unwrapping complicated shapes (such as cones and cylinders, even a sphere or ball). So, once you have learned how and where to place the seams on complex shapes, anything is possible.