(This pretty much helped me figure it out)
Pretty simple solution (I almost had it right to begin with): I was missing a few PowerMockito dependency jars (from https://code.google.com/p/powermock/wiki/Downloads?tm=2): Specifically {cglib-nodep-2.2.2.jar, javssist-3.18.1-GA.jar, objenesis-2.1.jar}.
It was a simple solution and kinda dumb mistake to begin with in the 1st place, since that powerMock googleCode download page has all of them: At 1st, when I had the problem, I had only downloaded and added powermock-mockito-1.5.4-full.jar; I already had the JUnit & Mockito jars, so I think that set of 3 let me write PowerMock code without any compile errors in Eclipse. The googlecode download page has the powermockito jar + dependecies in a zip, but also said powerockito jar available alone too. That situation made it kinda hard to realize I was missing some others since it appeared I had all I need from that perspective (thought I already had the dependencies I needed per my existing JUnit and Mockito jars).
In actuality, the zip with dependencies had the additional ones I needed to solve the problem. I should have double-checked that 1st, but didn't realize I made the opposite bad assumption.
So... answer is to make sure to get the zip with all dependencies [and add them all to your buildpath]. Kinda obvious and dumb in my part in the end, but hey, a lot of software bugs and problems end up being that: Simple bad assumptions or overlooked details we don't realize we made, and therefore take a while to realize when troubleshooting...