No, this is absolutely not just your problem! I am also an ESL and this very comment has been given to me numerous times: Your writing is weird, but I can't really tell how. After many years of working on it (including reading many books about writing, joining a writing group, publishing some papers, and writing pretty much everyday), my writing is still, well, weird. I have come to terms that I will never be able to conceal my "Asian-ness," and I'm fine with that.
Though, in the process, I did learn some tricks. I hope some of them will be useful to you.
Have basic grammar all nailed down
I understand that you are not seeking for grammatical advice. But people don't just judge your work's structure and suspect its lack of European thinking style from the get-go. Small mistakes such as (taken from your question) "By 'us' he meant European," and " I do have problems with my writing," can prompt readers to think of you as a foreign writer. And once that thought is sparked, a lot of scrutinies will follow.
Side notes: Some friends did give me very thorough diagnoses on my writing style, which may be useful to you: Generally I suffer from: i) lack of agreement between subjects and verbs, ii) wrong use of articles, and iii) lack of conjunctions and connectives. I have been working hard on addressing those problems, and it's probably going to be a life-long project which is fine by me.
Have him rewrite it
I'm an Asian student working with a European prof. My adviser told me
several times that when he read my writings (our papers), he just
wanted to rewrite it. He told me that my English was rather OK, but
"the way Oriental people think is different from us". By "us" he
Why not? Politely invite him to rewrite a few of your paragraphs. If he cannot name what is wrong, but he can rewrite it, then the solutions lie in the rewritten version. Schedule a meeting with him and go over the sticky parts. By that time he will have some ideas about your problems because after rewriting the piece, he will know what he has changed.
Even if he cannot give you any suggestion, with the two versions you can now easily show any writing coach what you wrote and what your instructor thought you wrote. The writing coach should be able to pinpoint the some basic stylistic differences.
Analyze articles' structure
When you read an article, read it a few times with different lenses. First, read for general sectioning, then read for information, and lastly read for its syntactic structure. A wonderful book that I have come across on this kind of analysis is Schimel's "Writing Science: How to Write Papers That Get Cited and Proposals That Get Funded." It provides tools and examples on dissecting an article from paragraph down to wording sequence in a sentence. There are many grammatically correct ways to put together a sentence, a paragraph, and an article; this book talks about the subtle effects of those different ways.
Do not start from your mother tongue
One old habit that I have successfully gotten rid of is to mentally draft a sentence in my mother tongue and then translate that into English. The process was counter-productive at best because the revision was quite time consuming and painful. A couple tricks helped me through the struggles:
Subject + Verb or
Subject + Verb + Object, then slowly add different modifiers. A wonderful book that teaches me most of these is Williams's Style: Toward Clarity and Grace. If you get a chance, please read it. I still read it time to time as a writing therapy.
Use a mind-map to gather ideas. Mind maps, in my opinion, operate very much in the way that scientists display ideas: using categories, hierarchies, relations, and lists. By focusing on this device, I could make the structure tighter and more coherent.
I have also grown bold enough to answer some writing-related questions on this site. Here are a few that you may find helpful:
Any place for people with fear of writing?
How can I best edit a paper to help get it published?
Good luck and keep working on it! Your (and my) problem is something that will not totally go away, but can definitely be lessened. Just enjoy the learning process and don't care too much about sounding 100% like a European thinker.