Can't seem to progress past where I am in my NG+, had no such problems on my first playthrough (Which was Emelita)

Anyway, info->Mission says "Talk to your friends": "To know more about Yuela you need to know more about the east. Talk to your friends, maybe you'll learn something."

However, no one is available to talk to. I've already completed her sword (Since it's NG+, store level is 10 and evaluation is 21735; so more than enough).

Under Info->Quest I have the following open:
* Clean Lake Shisetika (#29)
* Crayl's supplement (41#)
* Promise with an Angel (52#)
* Investigate the creature (64#)
* Substitute Shells (#65)
* Regroup and Reinforce (#86)
* Automatic Broom (#92)
* Soulseal Staff (#107)
* Shipwreck (#109)

For more or less all of those (aside from shipwreck), I'm fairly sure I can't progress further until the next chapter (??)- but if I'm wrong please tell me how to progress in them.

Did you carry over your character levels?

If not, make sure your characters are at the minimum required level to advance (see in the tips/tricks/useful information thread)

If you did keep their levels, look anyway, as maybe there are different requirements for the different storylines.

Or maybe you could try getting the Eushully characters with you (the Automatic Broom quest).

The quest says talk to your friends, but in a NG+, you have more friends than you did in the first playthrough. It's possible those count.

I've found the cause for this problem. Basically, I have 1 quest available in the plaza to go kill a level 90 (Erdgeist) which I simply can not yet do (Can't do more damage than he regenerates health).

Below this quest... I a quest to talk to yuela. Guess I'll just have to grind to hell and back until I'm high enough level to kill him... Or get bored of doing that and fail the quest.

There is a tactic that I would advice to you:
Choose 2 (or more) characters that have the most attack power and have combination attack from your team. Have Erdgeist or other difficult monster take place that let you surround him.
Now let's take Yuela, Serawi and Wil for example. Yuela and Wil will be attackers and Serawi will be defender. Placement of units will look somewhat like this:
W S
E Y
Now the fun begins. Equip Serawi with both Yuela's and Wil's Guardian. That will protect them a little in case of Erdgeist turn. Equip both Yuela and Wil with respective Guardian skills, combination attack and skills boosting attack power (if someone have Double Action, then in first turn have it equiped, and in second change it for other skill). You'll need to prapare some Ether Potions, because combination attack draws SP from both characters. It worked quite good for me.
Of course characters here were only an example, so you need to chose ones from your team that would work best. Guardian skills are helpful though, especially when monster have low hp (prevail is deadly skill).

/facepalm

Ah Goctionni I see you are still looking for that elusive Red Giant Skin. In retrospect i'll remember not to reference a mob you may never have seen before. It really was my bad.

You won't ever find a Cave Troll spawning from a portal in Monster Nest. Treasure Puttetos spawn at the beginning of the map, meaning it might be initially there but it won't spawn from a portal. The Cave Troll on the Monster Nest is the same in that regard. So in order to find him you save, load up the map (don't bother deploying) look around and if you see him go murder his face off. If you do not, then reload and try again.

I think you need to be at a higher chapter for Crayl's thing btw.

Sorry about all that.

Ah, thanks for that bit of information. I'll see if that helps

They are furniture, giving no merit.

Nope, the last reward from this chain is Clothesline, which is a spear with 40 str, -3 speed, wind element and Intimidate II.

By last quest in this chain I mean quest number 117, where you kill Quetzalcoatl

Managed to kill Erdgeist after I got Yuela to 70

Is QUetzalcoatl much more difficult than Erdgeist?

In my opinion he's waaaay easier. Actually, I killed him before he could even attack me (Serawi and her 9 range skill).