I find it really hard to try to speak Turkish with Turkish people who also speak English. I instantly get some kind of "speaking-block", nothing sensible comes out anymore, her kere sesim çıktı
But on the market or in the street, for example, where nobody knows me, I overcome that feeling quite easily. It's a real pain and so far I can't seem to help it

There are different reasons a language may be "hard" for a learner, and it's not all about grammar.

I learned Greek as a second language; Greek is not considered easy at all. Lots of irrgular verbs, complex declensions that change for different types of nouns, etc. And there is the ancient Greek element as well. However it was much easier to begin speaking, because although I would get verb/noun endings wrong, people always understood what I was saying. This is because the basic concepts of Greek and just about any other Indo-European language follow a similar pattern. Turkish, at least the actually Turkish part of the language, is very regular and logical. However the structure is so different that it requires lots of practice to get the brain around it. (Of course as I help some Turkish friends with English, I realize how confusing our structure can be to them...) On the other hand, Koreans tend to find Turkish pretty straightforward, because their language follows very similar patterns. (now pronunciation is another thing...)

Also because the language has evolved quite independently of western language and culture until recently, many expressions are quite foreign to us.

And lastly, I think unfortunately that many Turkish teachers don't teach very well. In universities the task is often thrust upon grad students without much actual language teaching experience, and they tend to teach Turkish as they were taught it - dissecting grammar. Remember "find the adverb" type exercises in English class? Education in Turkey is (again unfortunately) largely examination oriented. Memorize the information, choose the right answer. I remember going into 2nd year Turkish at a US university. The teacher entered the room, said "Welcome to 2nd-year Turkish. Let's start with some review. Ben öğretmenim. Sen nesin?" And out of 12 people who had studied Turkish for a year, there was not one person who could answer that question. 8| Because they had spent all their time reading and translating, and filling in blanks, rather than actually speaking!

I find it helps to avoid as much as possible trying to translate from English. Long sentences are particularly problematic for us because the places we can run on elegantly are quite different than in Turkish. And though in written Turkish we find things that are more like labyrinths than sentences most Turks don't actually talk that way. Pay attention to how they actually phrase things.

Find the things that give you trouble (relative clauses tend to be a real sticking point, or some of the "interesting" verb structures) and make your own exercises. Talk to yourself. Try and find simple texts; stuff for kids for example. The Internet is a great resource for this too. Find texts about things you know about. For example, if you are into cooking, look at the many many Turkish food sites. You'll get new vocabulary from context, and also get more comfortable with the way Turkish works. And keep practicing!

Getting your head round the sentance structure and the adding on of suffixes I find the most confusing. Time is a factor for me too! I dont have enough. And another problem I have is I tend to compare French and Spanish with Turkish although not so much now.

And in the UK, the selection of books, dictionaries etc is non-existant! The Red Book dictionary is so small I can't see the words properly - even with glasses.

But I will also persevere and hopefully be able to hold a conversation when I go to Turkey in June.