I have some characters I was thinking about starting an Impossible playthrough with. They are between levels 60-65. Do you think I would be struggle with this difficulty and these level characters?

I can't remember what level of strength that is, but I think that you should be fine. I am playing it through for the second time myself and all my characters are at level 99. Quite a few of my skills are at 99 as well. What I would say is that if you understand the accessories and which enemies are susceptible to which element, you should breeze through the majority of the game.
 
Just be prepared for the gold mecha and King Poo to make you cry.

What a crock of..., poo! Bugs like that are a pain in the butt.