Precedence matters, just change to:
Route::get('users',array('as'=> 'users', 'uses'=> 'UsersController@index'));
Route::get('users/new', array('as' => 'new_user', 'uses' => 'UsersController@create'));
Route::get('users/{id}', array('as' => 'user', 'uses' => 'UsersController@show') );
Route::get('users/{id}/edit', array('as' => 'edit_user', 'uses' => 'UsersController@edit') );
Route::post('users', 'UsersController@create');
Route::delete('users', 'UsersController@destroy');
Laravel assumed that 'new' was your {id} parameter.