If your code looks like this:
<?php
 namespace NS;
?>

...and you still get "Namespace declaration statement has to be the very first statement in the script" Fatal error, then you probably use UTF-8 encoding (which is good) with Byte Order Mark, aka BOM (which is bad). Try to convert your files to "UTF-8 without BOM", and it should be ok.

Regarding constants defined with define() inside namespaces...
define() will define constants exactly as specified. So, if you want to define a constant in a namespace, you will need to specify the namespace in your call to define(), even if you're calling define() from within a namespace. The following examples will make it clear.
The following code will define the constant "MESSAGE" in the global namespace (i.e. "\MESSAGE").
<?php
namespace test;
define('MESSAGE', 'Hello world!');
?>

The following code will define two constants in the "test" namespace.
<?php
namespace test;
define('test\HELLO', 'Hello world!');
define(__NAMESPACE__ . '\GOODBYE', 'Goodbye cruel world!');
?>

Expanding on @danbettles note, it is better to always be explicit about which constant to use.
<?php
 namespace NS;
 define(__NAMESPACE__ .'\foo','111');
 define('foo','222');
 echo foo; // 111.
 echo \foo; // 222.
 echo \NS\foo // 111.
 echo NS\foo // fatal error. assumes \NS\NS\foo.
?>

"A file containing a namespace must declare the namespace at the top of the file before any other code"
It might be obvious, but this means that you *can* include comments and white spaces before the namespace keyword.
<?php
// Lots 
// of
// interesting
// comments and white space
namespace Foo;
class Bar {
}
?>

namespace statement is defined at first of the php files. But 
 before namespace declaration only three elements allowed.
 1.declare statement
 2.spaces
 3.comments

You should not try to create namespaces that use PHP keywords. These will cause parse errors. 
Examples:
<?php
namespace Project/Classes/Function; // Causes parse errors
namespace Project/Abstract/Factory; // Causes parse errors
?>

Please note that a PHP Namespace declaration cannot start with a number.
It took some time for me to debug...

@ RS: Also, you can specify how your __autoload() function looks for the files. That way another users namespace classes cannot overwrite yours unless they replace your file specifically.

Namespace name are case-insensitive.
namespace App
and
namespace app
are same meaning.
Besides, Namespace keword are case-insensitive.
Namespace App
namespace App
and
NAMESPACE App
are same meaning.

There is nothing wrong with PHP namespaces, except that those 2 instructions give a false impression of package management.
... while they just correspond to the "with()" instruction of Javascript.
By contrast, a package is a namespace for its members, but it offers more (like deployment facilities), and a compiler knows exactly what classes are in a package, and where to find them.