Что понимается под Build/Rebuild?
Какой проект - чисто Java/J2EE?

Странно.
У меня стоит Build Automatically и я никогда не сталкивался с проблемой того, что какой-то класс не откомпилировался при сохранении его изменений.

Это цитата из help:

Builds
A build is a process that derives new resources from existing ones, updates existing resources, or both.

In the Workbench, different builders are invoked for different types of projects. For example, when a build is triggered for a Java project, a Java builder converts each Java source file (.java files) into one or more executable class files (.class files). Builders usually enforce the constraints of some domain. For example, a Web link builder could update links to files whose name/location changes.

There are two kinds of builds:

An incremental build leverages a previously built state and applies the transforms of the configured builders to the resources that have changed since the previous state was computed (that is, since the last build).

A full build (or rebuild) discards any previously built state and transforms all requested resources according to the domain rules of the configured builders. The first incremental build is equivalent to a full build as there is no previous state to work from.

Full and incremental builds can be done over a specific set of projects or the workspace as a whole. Specific files and folders cannot be built. There are two ways that builds can be performed:

Automatic builds are performed as resources are saved. Automatic builds are always incremental and always operate over the entire workspace. You can configure your Workbench preferences (Window > Preferences > Workbench) to perform builds automatically on resource modification.
Manual builds are initiated when you explicitly select a menu item or press the equivalent shortcut key. Manual builds can be either full or incremental and can operate over collections of projects or the entire workspace.

Почисти bin-директорию и будет полный rebuild.

Другое дело, что Build не освобождает от необходимости пересборки jar-ов. По крайней мере я этому не научился и приходится еще для EJB делать Run XDoclet/Run Packaging/Redeploy.

Очень странно. Я такого у себя не замечал.

Столкнулся буквально сейчас с трудностью другого плана: добавил в проект новый package, перебросил туда часть классов, пересобрал jar, делаю Deploy - JBoss не видит все классы, которые оказались в новом pakage. Крутил-вертел, оказалось, что забыл исправить конфигурацию XDoclet (не включил новую директорию в include).

У меня Eclipse на Windows2000.

Попробуй поискать на http://%5D%7C>]http://]|> www.eclipse.org в community, может там чего найдешь

Только что столкнулся с такой же проблемой.

Решение:
1- Убил все, что под директорией bin, где у меня откомпилированные классы (это я как в Tutirial сделал в XDoclet настройках).
2- Project->Clean. Указал мой проект и он все перекомпилировал. При этом было включено Project->Build Automatically.