It sounds like you recently changed your diet pretty dramatically. When I first started PB-ing, and again at the beginning of this year, when I cut carbs drastically- My cycles got weird. Super weird. Specifically, what was typically a textbook 28 day tour stretched out to 50, 55 days. Eventually, it self-regulated back to "normal." Your body may be trying to process everything and catch up, but you are right to be concerned, as there are a lot of variables at work here.
Please don't beat yourself up about your weight- my guess is that the gyno visit may clear some things up- either figuring out if there is a problem, or putting your mind at ease that there isn't. It sounds like your hormonal levels are going haywire. The IUD removal sounds like a good idea to me, too. Hang in there! I know, that helpless feeling is the worst.
In the meantime, you need to find a new doctor. Have you gone to an endocrinologist, or considered a naturopath? (I know, granola crunchy, but can't help it- I'm from California!) There is a list of Paleo/Primal-friendly practitioners around here somewhere. Please let us know how your appointment goes!