Xbox and Xbox Live are the same thing. What it means is that they have special certification that allows them to connect to Xbox Live. This includes achievements for which you'll earn points on Xbox Live and access to leaderboards.
The problem is that this certification is incredibly difficult and time consuming to attain. You may also end up bound by certain conditions. So most small developers avoid it altogether. Big developers and publishers have the influence and time to devote to getting through that certification. That's why you'll find that most games from big publishers, EA, Gameloft, and Nokia have that certification.
When you see Nokia branded games, all it means is that they're the distributor on Windows Phone, not that they actually developed the game. Given that they actually make Windows Phone devices the certification process is likely easiest for them.