but I have never come across someone who is English that can speak fluently in Polish and understand others competently.
In my experience Americans are generally better at learning Polish than British or Irish people are (there are some exceptions both ways of course).
I remember at one time knowing about 4 or 5 Americans (no contact with the language in the US) who were fluent enough in Polish to deal with bureaucracy on their own with no interpreter. I knew a similar number of Brits at the same time who'd been in Poland for similar lengths of time and none of them could speak Polish for crap.
IME Polish is much easier to learn in situ rather than in another country. The learning curve is _very_ steep in the beginning and for the first two years or so it just seems like a hodgepodge of exceptions rather than a system. It's sometime in the third year it starts becoming a bit easier. The problem is you need an overview of the whole system and how it works before you can make much sense of it but once you have that you can predict things pretty well.
(English works in the opposite manner, it starts easy and then after a couple of years starts getting harder and harder).
My advice is first and foremost concentrate on nouns, pronouns and adjectives. For many people that seems to be counter-intuitive and they want to spend more time of verbs in the beginning. But the case system is really the backbone of the language. It should be the priority (don't neglect verbs entirely but don't go crazy over them in the beginning, the more you understand the noun system the easier verbs will be).
Whatever you do, don't spend a lot of time memorizing "aspect pairs" of verbs that's all but useless. I wasted a lot of time learning lists but the more I learned the less I thought about aspect (it largely takes care of itself in advanced learning).
Is Polish up there with the MOST difficult language to learn?
No. The old US Airforce classification (specialized for Americans) put it in category 3, harder than French or Spanish (1) or German (2) but easier than Chinese or Arabic languages (4).