The common English phrase "I'm beginning to think that ..." is kind of a standard or set phrase, and the meaning does not normally change with context. It is not in any way a uniquely American expression, as it's used by all English speakers. It simply means:
I have recently had the particular thought that ...
or
My thoughts have recently included certain things such as ...
This structure can be used with many cognitive verbs:
I'm beginning to feel that ...
I'm beginning to understand that ...
I'm beginning to suspect that ...
The difference between "I'm beginning to think that ..." and "I'm thinking that ..." is the nuance of recent or just started. It often implies a change in thought based on new information.
And yesterday I was sure I tasted arsenic in my afternoon tea. I can't be sure, Holmes, but I'm beginning to think that my wife doesn't love me any more.