The main thing is it isn't just more of the same gameplay. Many of the levels have entirely new challenges to them, some of which are rather difficult. For example, on one, you have to use your katamari to bring a fire to a campground. The difficulty is that you need to keep on collecting combustible things to keep the fire lit, while collecting noncombustible things to make the katamari actually grow (so it'll be big enough to ignite the wood pile).
Another tricky level is underwater. Motion is very different than above ground so you need a different strategy in how you move around. Plus, there are fishermen whose hooks will snag you from time to time.
I haven't gotten to the point where I need to hook an oscillating fan up to my controller yet but the game is definitely quite different than the first, while staying true to its roots. Also, the soundtrack is at least as awesome as the first one!