app.js

// the module needs to be `define`'d. If the `require([])` syntax is used, then the async method NEEDS to be used.
define(['jquery', 'underscore', 'backbone'], function($, _, Backbone) {
  console.log("running the app...");

  var initialize = function(){
    // Pass in our Router module and call it's initialize function
    console.log("initializing from inside the app");
  };

  return {
    initialize: initialize
  };
});

main.js

require.config({
  paths: {
    jquery: 'libs/jquery',
    underscore: 'libs/underscore',
    backbone: 'libs/backbone'
  },
  shim: {
    backbone: {
      deps: ['underscore', 'jquery'],
      exports: 'Backbone'
    }
  }
});

require(['app'], function(App) {
  console.log("requiring app");
  App.initialize();
});

Try channging the exports for the backbone shim to 'backbone' instead of 'Backbone'

Are you sure that you have the proper AMD versions of backbone and underscore? I remember seeing something similar using the stock versions of the libraries.

Try: https://github.com/amdjs/underscore and https://github.com/amdjs/backbone

The solution involves this: http://requirejs.org/docs/errors.html#notloaded. The code changes should make it seem obvious